应用： 树状数组一般用来求区间的和，适合于给出一连串的数，多次求区间的和和以及多次更新某个位置的数 算法过程： 预处理： 对于:a[1],a[2],a[3] .....a[N];（求a数组中某区间的和） 定义函数lowbit(i)=i&(i^(i-1); 可得lowbit=pow(2,k),k为i的二进下制下末尾的0的个数 c[i]=a[i-lowbit(i)+1]+a[i-lowbit(i)+2]+a[i-lowbit(i)+3]...a[i]; 伪代码： for i to n do j:=i-lowbit(i)+1; c[i]:=0; for j to i do c[i]:=c[i]+a[j]; 求区间和： 求区间[from,to]的和： 可得ans=sum[to]-sum[from-1]; sum(k)=c[N1]+c[N2]+c[N3]....c[Nm];（Nm>0) N1=k; Ni-1=Ni-lowbit(Ni); 伪代码： ni=k; ans:=0; while(ni>0) { ans:=ans+c[ni]; ni-=lowbit(ni);(ni每次将二进制下最右边的1变成0) } sum(k)=ans; 复杂度为O（log(k)) INT（log(k)）＋1可理解为k二进制下的位数 （INT为取整） 数据更新: a[i]的数据更新,则c[Ni],c[Ni+1],c[Ni+2]....c[Nm];(Nm<=n) Ni+1=Ni+lowbit(Ni); 伪代码： ni=i; ans=0; while(ni>0) { ans:=ans+c[ni]; ni:=ni+lowbit(ni);(ni二进制下最右边的1向前进1位直到为N) } 复杂度为(log(N)); (N=length(a));
示例代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN=1000; int a[MAXN+5]; int c[MAXN+5]; void BuildTreeArray() { int i; int begin; int j; for(i=1;i<=MAXN;i++) { begin=i-(i&(i^(i-1)))+1; for(j=begin;j<=i;j++) { c[i]+=a[j]; } } } void update(int position,int value) { int ni=position; while(ni<=MAXN) { c[ni]-=a[position]; c[ni]+=value; ni+=(ni&(ni^(ni-1))); } } int sum(int end) { int ni; int ans; ans=0; ni=end; while(ni>0) { ans+=c[ni]; ni-=(ni&(ni^(ni-1))); } return ans; } int main() { int i; int from,to; int ansfrom; int ansto; int UpdatePosition; int UpdateValue; // FILE* file; // file=freopen("testdata.cpp","r",stdin); for(i=1;i<=MAXN;i++) { scanf("%d",&a[i]); } memset(c,0,sizeof(c)); BuildTreeArray(); char ch[10]; // fclose(stdout); while(scanf("%s",ch)) { if(strcmp(ch,"update")==0) { scanf("%d %d",&UpdatePosition,&UpdateValue); update(UpdatePosition,UpdateValue); // a[UpdatePosition]=UpdateValue; } else if(strcmp(ch,"sum")==0) { scanf("%d %d",&from,&to); ansfrom=sum(from-1); ansto=sum(to); /* int testans=0; for(i=from-1;i<=to;i++) { testans+=a[i]; } printf("%d/n",testans);*/ printf("%d/n",ansto-ansfrom); } } return 0; }
