交互式网站开发技术,网站排名优化建设,常德农科院网站,重庆 手机网站制作by wyl8899 树状数组的基本知识已经被讲到烂了#xff0c;我就不多说了#xff0c;下面直接给出基本操作的代码。
假定原数组为a[1..n]#xff0c;树状数组b[1..n]#xff0c;考虑灵活性的需要#xff0c;代码使用int *a传数组。
#define lowbit(x) ((x)(-(x))…
by wyl8899 树状数组的基本知识已经被讲到烂了我就不多说了下面直接给出基本操作的代码。
假定原数组为a[1..n]树状数组b[1..n]考虑灵活性的需要代码使用int *a传数组。
#define lowbit(x) ((x)(-(x)))int sum(int *a,int x){int s0;for(;x;x-lowbit(x))sa[x];return s;}void update(int *a,int x,int w){for(;xn;xlowbit(x))a[x]w;}
sum(x)返回原数组[1,x]的区间和update(x,w)将原数组下标为x的数加上w。
这两个函数使用O(操作数*logn)的时间和O(n)的空间完成单点加减区间求和的功能。 接下来做一些升级让树状数组完成区间加减单点查询的功能。
直接做的话很困难需要对问题做一些转化。
考虑将原数组差分即令d[i]a[i]-a[i-1]特别地d[1]a[1]。
此时a[i]d[1]..d[i]所以单点查询a[i]实际上就是在求d数组的[1..i]区间和。
而区间[l,r]整体加上k的操作可以简单地使用d[l]k和d[r1]-k来完成。
于是我们用树状数组来维护d[]就可以解决问题了。 下面再升级一次完成区间加减区间求和的功能。
仍然沿用d数组考虑a数组[1,x]区间和的计算。d[1]被累加了x次d[2]被累加了x-1次...d[x]被累加了1次。
因此得到
sigma(a[i])
sigma{d[i]*(x-i1)}
sigma{ d[i]*(x1) - d[i]*i }
(x1)*sigma(d[i])-sigma(d[i]*i)
所以我们再用树状数组维护一个数组d2[i]d[i]*i即可完成任务。
POJ 3468就是这个功能的裸题下面给出代码。
[请注意我们上面的讨论都假定了a[]初始全是0。如果不是这样呢?下面的程序里给出了一个相对简便的处理办法。]
// POJ 3468 Using BIT#include cstdioconst int maxn100010;__int64 a[maxn],b[maxn],c[maxn];int n,m;inline int lowbit(const int x){return x(-x);}__int64 query(__int64 *a,int x){__int64 sum0;while(x){suma[x];x-lowbit(x);}return sum;}void update(__int64 *a,int x,__int64 w){while(xn){a[x]w;xlowbit(x);}}int main(){int l,r,i;__int64 ans,w;char ch;scanf(%d%d,n,m);a[0]0;for(i1;in;i){scanf(%I64d,a[i]);a[i]a[i-1];}while(m--){scanf(%c,ch);while(ch!Q ch!C)scanf(%c,ch);if(chQ){scanf(%d%d,l,r);ansa[r]-a[l-1](r1)*query(b,r)-l*query(b,l-1)-query(c,r)query(c,l-1);printf(%I64d\n,ans);}else{scanf(%d%d%I64d,l,r,w);update(b,l,w);update(b,r1,-w);update(c,l,w*l);update(c,r1,-(r1)*w);}}return 0;}
[当a[]初始不全0的时候我们就只维护后来加上去的部分查询区间和的时候再补上初始的时候这一段的区间和就可以了。]
一维到二维的分割线
接下来到二维树状数组。
先看看sum和update变成什么样子了吧。
inline int gs(int a[maxn][maxn],int x,int y){int s0,t;for(;x;x-lowbit(x))for(ty;t;t-lowbit(t))sa[x][t];return s;}inline void gp(int a[maxn][maxn],int x,int y,int w){int t;for(;xn;xlowbit(x))for(ty;tm;tlowbit(t))a[x][t]w;}
gs就是sumgp就是update由于需要多次调用的缘故改成了更短的名字。
单点加减矩形求和并不难直接用上面的两段就行了。
需要注意的是矩形的求和怎么求。上面的代码返回的是(1,1)-(x,y)矩形的和。
那么(x1,y1)-(x2,y2)的矩形和由下式给出
sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)sum(x1-1,y1-1)
画个图就很好理解了。 对于涉及矩形加减的情形我们发现一维中的差分的办法在二维的情况用不出来所以要改一下。思考一下一维中的差分的另外一个含义d[i]同时也表示d[i..n]的整体增量d[i]k就意味着把d[i]..d[n]全部加上了k。理解了之后就发现这个意义上可以推广到二维仍假设原矩形初始全为0以便接下来的叙述。
令a[x,y]表示(x,y)-(n,m)矩形的整体增量其中(n,m)是边界。
那么(x1,y1)-(x2,y2)矩形整体加k的代码就是
gp(a,x1,y1,w); gp(a,x21,y1,-w);gp(a,x1,y21,-w); gp(a,x21,y21,w);
仍然是建议画个图来帮助理解。 至此矩形加减单点查询的问题得到了解决。 重头戏在这里矩形加减矩形求和。
求原矩形(1,1)-(x,y)的和结果由下式给出
sigma(i1..x,j1..y) a[i,j]*(x-i1)*(y-j1)
很好理解吧? 但是这个式子并不是那么容易求和的展开一下求和的部分得到
a[i,j]* ( (x1)(y1) - (x1)*j - (y1)*x i*j )
整个式子就是
(x1)(y1)sigma(a[i,j]) - (x1)sigma(a[i,j]*j) - (y1)sigma(a[i,j]*i) sigma(a[i,j]*i*j)
知道怎么处理了吧如果没有请回去复习一维的处理方法。
令b[i,j]a[i,j]*i c[i,j]a[i,j]*j d[i,j]a[i,j]*i*j
维护a,b,c,d一共四个二维树状数组问题得到解决。
tyvj p1716就是实现这两个功能的裸题下面给出完整代码。 // tyvj p1716 using 2D BIT#includecstdio#includecstring#define lowbit(x) ((x)(-(x)))const int maxn2049;int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn];int n,m;inline int gs(int a[maxn][maxn],int x,int y){int s0,t;for(;x;x-lowbit(x))for(ty;t;t-lowbit(t))sa[x][t];return s;}inline void gp(int a[maxn][maxn],int x,int y,int w){int t;for(;xn;xlowbit(x))for(ty;tm;tlowbit(t))a[x][t]w;}inline int sum(int x,int y){return (x1)*(y1)*gs(a,x,y)-(y1)*gs(b,x,y)-(x1)*gs(c,x,y)gs(d,x,y);}inline void update(int x1,int y1,int x2,int y2,int w){gp(a,x1,y1,w); gp(a,x21,y1,-w);gp(a,x1,y21,-w); gp(a,x21,y21,w);gp(b,x1,y1,w*x1); gp(b,x21,y1,-w*(x21));gp(b,x1,y21,-w*x1); gp(b,x21,y21,w*(x21));gp(c,x1,y1,w*y1); gp(c,x21,y1,-w*y1);gp(c,x1,y21,-w*(y21)); gp(c,x21,y21,w*(y21));gp(d,x1,y1,w*x1*y1); gp(d,x21,y1,-w*(x21)*y1);gp(d,x1,y21,-w*x1*(y21)); gp(d,x21,y21,w*(x21)*(y21));}int main(){int x1,y1,x2,y2,w;char ch;scanf(%c,ch);while(ch!X)scanf(%c,ch);scanf(%d%d\n,n,m);memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(d,0,sizeof(d));while(scanf(%c,ch)!EOF){scanf(%d%d%d%d,x1,y1,x2,y2);if(chL){scanf(%d\n,w);update(x1,y1,x2,y2,w);}else{scanf(\n);printf(%d\n,sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)sum(x1-1,y1-1));}}return 0;}
wy18899
没原文链接只能写个原创但是不是我写的
