二维树状数组模板（自用）

本文主要是介绍二维树状数组模板（自用），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

demo：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<queue>
 6 #include<cstdio>
 7 #define LL long long 
 8 using namespace std;
 9 const int maxa=1024*2+10;//~~pow(2,11)+10
10 LL n,m;
11 LL C1[maxa][maxa],C2[maxa][maxa],C3[maxa][maxa],C4[maxa][maxa];//开辟四个树状数组用于维护 
12 LL lowbit(LL i){
13     return i&-i;
14 }
15 void add(LL a,LL b,LL k){
16     for(LL i=a;i<=n;i+=lowbit(i))
17         for(LL j=b;j<=m;j+=lowbit(j)){ 
18             C1[i][j]+=k;
19             C2[i][j]+=k*a;
20             C3[i][j]+=k*b;
21             C4[i][j]+=k*a*b;
22     } 
23 }
24 LL sum(LL x,LL y){
25     LL ans=0;
26     for(LL i=x;i>0;i-=lowbit(i))
27         for(LL j=y;j>0;j-=lowbit(j))
28             ans+=(x+1)*(y+1)*C1[i][j]-(y+1)*C2[i][j]-(x+1)*C3[i][j]+C4[i][j];
29     return ans;
30 }
31 int main(){
32     scanf("%lld%lld",&n,&m);
33     LL op,a,b,c,d,k; 
34     while(scanf("%lld",&op)!=EOF){
35         if(op==1){
36             scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
37             add(a,b,k);
38             add(c+1,d+1,k);
39             add(c+1,b,-k);
40             add(a,d+1,-k);
41             //一维差分数组应该为：add(x,k),add(y+1,-k); 
42         }
43         else if(op==2){
44             scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
45             printf("%lld\n",sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1));//对于区间更新的查询 
46         }
47     }
48     return 0;
49 }

这篇关于二维树状数组模板（自用）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！