二維樹狀數(shù)組模板(區(qū)間修改+區(qū)間查詢)

例題：JOIOI上帝造題的七分鐘
一共兩種操作：

\(L\ x_1\ y_1\ x_2\ y_2\ d\)：把\((x_1,y_1)\)，\((x_2,y_2)\)這個矩形內(nèi)所有元素加\(d\)。
\(k\ x_1\ y_1\ x_2\ y_2\)：查詢\((x_1,y_1)\)，\((x_2,y_2)\)這個矩形內(nèi)所有元素的和。

代碼如下：

#include<bits/stdc++.h> #define RG register #define IL inline #define _ 2050 #define ll long long //#define ll int using namespace std;ll n , m , c1[_][_],c2[_][_],c3[_][_],c4[_][_] ;IL void upt(ll x , ll y , ll dt){for(RG int i = x; i <= n; i += (i & -i) )for(RG ll j = y; j <= m; j += (j & -j)){c1[ i ][ j ] += dt ;c2[ i ][ j ] += dt * y;c3[ i ][ j ] += dt * x;c4[ i ][ j ] += dt * x * y;} } IL ll calc(ll x,ll y){RG ll res = 0;for(RG ll i = x; i > 0; i -= (i & -i))for(RG ll j = y; j > 0; j -= (j & -j)){res = res+ (x + 1) * (y + 1) * c1[ i ][ j ]- (x + 1) * c2[ i ][ j ]- (y + 1) * c3[ i ][ j ]+ c4[ i ][ j ] ; }return res; }IL void add(ll X1,ll Y1,ll X2,ll Y2,ll dt){upt(X1 , Y1 , dt ) ;upt(X2 + 1 , Y1 , -dt ) ;upt(X1 , Y2 + 1, -dt ) ;upt(X2 + 1, Y2 + 1, dt ) ; } IL ll query(ll X1,ll Y1,ll X2,ll Y2){returncalc(X2 , Y2) + calc(X1 - 1, Y1 - 1) -calc(X1 - 1 , Y2) - calc(X2 , Y1 - 1) ; }int main(){ll X1 , X2 , Y1 , Y2 , z; char c[3]; scanf("X %lld %lld",&n,&m);while(scanf("%s",c)!=EOF){scanf("%lld%lld%lld%lld", &X1, &Y1, &X2, &Y2);if(c[0]=='L'){scanf("%lld", &z);add(X1 , Y1 , X2 , Y2 , z);}else printf("%lld\n",query(X1 , Y1 , X2 , Y2 ));}return 0;return 0;}

轉(zhuǎn)載于:https://www.cnblogs.com/Guess2/p/8459568.html

總結(jié)

以上是生活随笔為你收集整理的二维树状数组模板(区间修改+区间查询)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。