资源描述：
《树状数组万能讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、[数据结构]树状数组专题做数据结构的题真是异常的能让人感到自己在脱菜的路上迈进啊。这一次来看看树状数组。 树状数组的基本知识已经被各种大牛和菜鸟讲到烂了，我就不多说了，下面给出基本操作的代码。假定原数组为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,int
2、w){ for(;x<=n;x+=lowbit(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]。那么区间[l,r]整体加上k的操作就可以简单地使用d[l]+=k;d[r+1]-=k来完成了。此时a[i]=d[1]+..+d[i]，所以单
3、点查询a[i]实际上就是在求d数组的[1..i]区间和，很容易完成了。 下面再升级一次，完成区间加减，区间求和的功能。仍然沿用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)所以我们再用树状数组维护一个数组d2[i]=d[i]*i，即可完成任务。POJ3468就是这个功
4、能的裸题...下面给出代码：//POJ3468 UsingBIT #include constintfin=0,maxn=100010;__int64a[maxn],b[maxn],c[maxn];intn,m; inlineintlowbit(constint&x){ returnx&(-x); } __int64query(__int64*a,intx){ __int64sum=0; while(x){sum+=a[x];x-=lowbit(x);} returnsum; } void
5、update(__int64*a,intx,__int64w){ while(x<=n){a[x]+=w;x+=lowbit(x);} } intmain(){ intl,r,i; __int64ans,w; charch; if(fin){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); } scanf("%d%d",&n,&m); a[0]=0; for(i=1;i<=n;++i){ scanf("%I64d",&a[i]); a[i]+=a
6、[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); updat
7、e(b,l,w); update(b,r+1,-w); update(c,l,w*l); update(c,r+1,-(r+1)*w); } } if(fin){ fclose(stdin);fclose(stdout); } return0;}====================================一维到二维的分割线=======================================接下来到二维树状数组。先看看sum和update变成什么样子了吧。inlineintgs(int
8、a[maxn][maxn],intx,inty){ 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; f
