树状数组维护区间和的模型及其拓广的简单总结

《树状数组维护区间和的模型及其拓广的简单总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树状数组维护区间和的模型及其拓广的简单总结bywyl8899树状数组的基本知识已经被讲到烂了，我就不多说了，下面直接给出基本操作的代码。假定原数组为a[1..n]，树状数组b[1..n]，考虑灵活性的需要，代码使用int*a传数组。#definelowbit(x)((x)&(-(x)))intsum(int*a,intx){ints=0;for(;x;x-=lowbit(x))s+=a[x];returns;}voidupdate(int*a,intx,intw){for(;x<=n;x+=lowb

2、it(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

3、,r]整体加上k的操作，可以简单地使用d[l]+=k和d[r+1]-=k来完成。于是，我们用树状数组来维护d[]，就可以解决问题了。下面再升级一次，完成区间加减，区间求和的功能。仍然沿用d数组，考虑a数组[1,x]区间和的计算。d[1]被累加了x次，d[2]被累加了x-1次，...，d[x]被累加了1次。因此得到sigma(a[i])=sigma{d[i]*(x-i+1)}=sigma{d[i]*(x+1)-d[i]*i}=(x+1)*sigma(d[i])-sigma(d[i]*i)所以我们再用树

4、状数组维护一个数组d2[i]=d[i]*i，即可完成任务。POJ3468就是这个功能的裸题，下面给出代码。[请注意我们上面的讨论都假定了a[]初始全是0。如果不是这样呢?下面的程序里给出了一个相对简便的处理办法。]//POJ3468UsingBIT#includeconstintmaxn=100010;__int64a[maxn],b[maxn],c[maxn];intn,m;inlineintlowbit(constint&x){returnx&(-x);}__int64query

5、(__int64*a,intx){__int64sum=0;while(x){sum+=a[x];x-=lowbit(x);}returnsum;}voidupdate(__int64*a,intx,__int64w){while(x<=n){a[x]+=w;x+=lowbit(x);}}intmain(){intl,r,i;__int64ans,w;charch;scanf("%d%d",&n,&m);a[0]=0;for(i=1;i<=n;++i){scanf("%I64d",&a[i]);a[

6、i]+=a[i-1];}while(m--){scanf("%c",&ch);while(ch!='Q'&&ch!='C')scanf("%c",&ch);if(ch=='Q'){scanf("%d%d",&l,&r);ans=a[r]-a[l-1]+(r+1)*query(b,r)-l*query(b,l-1)-query(c,r)+query(c,l-1);printf("%I64d",ans);}else{scanf("%d%d%I64d",&l,&r,&w);update(b,l,w);

7、update(b,r+1,-w);update(c,l,w*l);update(c,r+1,-(r+1)*w);}}return0;}[当a[]初始不全0的时候，我们就只维护后来加上去的部分，查询区间和的时候再补上初始的时候这一段的区间和就可以了。]======================一维到二维的分割线=========================接下来到二维树状数组。先看看sum和update变成什么样子了吧。inlineintgs(inta[maxn][maxn],intx,inty

8、){ints=0,t;for(;x;x-=lowbit(x))for(t=y;t;t-=lowbit(t))s+=a[x][t];returns;}inlinevoidgp(inta[maxn][maxn],intx,inty,intw){intt;for(;x<=n;x+=lowbit(x))for(t=y;t<=m;t+=lowbit(t))a[x][t]+=w;}gs就是sum，gp就是update，由于需要多次调用的缘故，改成了更短的名字。单点加减，矩形求和并