二维树状数组几种模板

2019-04-14 18:58发布

站内文章 / 模拟电子
13406 0 1582
1.单点更新，区间查询 int tree[N][N]; //行列分开看，每一行每一列都是一个一维树状数组 int n,m; //n行m列 int lowbit(int x){return x&(-x);} //单点更新,区间查询 void add(int x,int y,int val){ //单点更新 while(x<=n){ for(int i=y;i<=m;i+=lowbit(i)){ //列的一维树状数组 tree[x][i]+=val; } x+=lowbit(x); } } int sum(int x,int y){ //返回(0,0,),(x,y)为对角顶点的矩阵和 int res=0; while(x>0){ for(int i=y;i>0;i-=lowbit(i)){ res+=tree[x][i]; } x-=lowbit(x); } return res; } int query(int x1,int y1,int x2,int y2){ //区间查询 return sum(x2,y2)+sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2); //容斥,注意是否可能超longlong } 2.区间更新，单点查询 //区间修改,单点查询,和一维树状数组差分思想一样,差分思想。 //二维前缀和： //sum[i][j]=sum[i−1][j]+sum[i][j−1]−sum[i−1][j−1]+a[i][j] //那么我们可以令差分数组d[i][j] 表示 a[i][j] 与 a[i−1][j]+a[i][j−1]−a[i−1][j−1] 的差。 void regionUpdate(int x1,int y1,int x2,int y2,int val){ add(x1,y1,val); add(x2+1,y1,-val); add(x1,y2+1,-val); add(x2+1,y2+1,val); } int pointQuery(int x,int y){ return sum(x,y); 3.区间更新，区间查询 ll n, m, Q; ll t1[N][N], t2[N][N], t3[N][N], t4[N][N]; void add(ll x, ll y, ll z){ for(int X = x; X <= n; X += X & -X) for(int Y = y; Y <= m; Y += Y & -Y){ t1[X][Y] += z; t2[X][Y] += z * x; t3[X][Y] += z * y; t4[X][Y] += z * x * y; } } void range_add(ll xa, ll ya, ll xb, ll yb, ll z){ //(xa, ya) 到 (xb, yb) 的矩形 add(xa, ya, z); add(xa, yb + 1, -z); add(xb + 1, ya, -z); add(xb + 1, yb + 1, z); } ll ask(ll x, ll y){ ll res = 0; for(int i = x; i; i -= i & -i) for(int j = y; j; j -= j & -j) res += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] - (x + 1) * t3[i][j] + t4[i][j]; return res; } ll range_ask(ll xa, ll ya, ll xb, ll yb){ return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1); } 可以看这个巨巨的博客，太强了，qaq，%%% 博客链接：https://www.cnblogs.com/RabbitHu/p/BIT.html

热门文章