一维树状数组
笔者眼中的一维树状数组
一维树状数组，是一棵左偏树，他的每一个节点，维护的是一段区间的和,若该节点的 下标为i，那么他维护的区间就是(i&(i-1),i] ，熟悉位运算的人应该都知道，i&(i-1)与i的关系：i&(i-1)和i去掉i的二进制中的最低位的1后的值 相等。并且，树状数组就是做单点修改，前缀区间查询的数据结构。 为了利 于描述，下文暂时称一维树状数组为树状数组树状数组询问操作
原数组的前缀区间查询，根据定义，我们很容易知道，区间[1,x] 一定能够被树状数组的某些节点所表示的区间 并来表达，且唯一表达，且表达式最多lg(x)项，因为x的二进制中最多lg个1。于是任意前缀区间就能够在树状数组中查询得到。树状数组更新操作
原数组的点修改，我们必须找到所有包含了该点的树状数组节点，若要修改的点的下标为i，根据定义我们解不等式 (x&(x-1))+1<=i<=x,可以证明可以证明如果a是一个解，且存在另一个大于a的最小的解b，则b=a+a&-a。于是我们根据此操作 一步一步去更新树状数组节点即可，此节点数目lg级别树状数组的用途
根据定义，我们可以很容易的维护很多关于单点修改，前缀区间查询的操作，比如前缀最值、 前缀区间和。区间加法与区间减法
如果对于作用于区间[x,y]上的区间运算f(x,y)满足 若对于所有的a<b<=c可以根据f(a,b-1)和f(b,c)算出 f(a,c)，则此运算满足区间加法如果对于作用于区间[x,y]上的区间运算f(x,y)满足 若对于所有的a<b<=c可以根据f(a,c)和f(b,c)算出 f(a,b-1)，则此运算满足区间减法
让用途更广
对于所有满足区间减法的操作，比如说:区间和，区间异或和。我们可以根据前缀区间 相减，得到任意区间的区间和与区间异或和。差分操作
如果我们要对一个区间进行修改，我们有这样一种做法，在区间起点加一个标记，在区间末尾 再加一个标记，于是我们就表面修改了此数组的一个区间,查询的话，查前缀和就可以了，由于本文重点不在此，简要 举个例子，对于一个数组，我们如果说要经常修改某些区间的值:整个区间的所有元素加上一个d，我们可以考虑这样做，让区间起点+d,区间末尾右边的元素-d, 当修改完之后，我们对此数组做一遍前缀和就能得到修改结果。我们称表面修改的数组为差分数组，差分数组的前缀和就是我们要的原数组。再广一点
考虑一个维护区间和的数组，如果要对随机区间修改，对单点查询怎么办呢？我们维护此数组 的差分数组，原数组的区间修改就是差分数组的点修改，原数组的点查询就是差分数组的前缀区间查询，于是我们解决了这个问题还能更加广
如果我们不仅仅满足与点查询，我们还要前缀和区间查询，也能办到，再来理一下，原数组的前缀 和区间查询等于差分数组的二阶前缀和区间查询，我们假定a为差分数组：这里很明显了，我们维护一个原数组的差分数组ai和另一个数组i*ai的点修改区间查询即可。
二维树状数组
提升纬度
我们定义,在二维数据结构中，让点(x,y)维护点(x&(x-1)+1,y&(y-1)+1)到(x,y)的矩阵的区间信息，根据 之前的推导，使用类似的方法，可以得出在每一维上最多lg个节点，故两维一起最多lg*lg个节点。类似的也可以得出更新的时候，节点依旧是lg*lg个。二维的差分和任意区间维护此处不做细分析
如果我们维护了二维前缀区间定义前缀区间为:(1,1)到(x,y) 的矩形区间。的信息，根据容斥原理，任意区间很容易算出来了，差分是一样的。二维的区间修改，区间和查询
一样的，是差分数组的二阶前缀和，化简公式如下:于是我们维护四个普通树状数组即可
struct Binary_Indexed_Tree{ //点更新区间查询,最大可用范围[1,N），实际使用[1,n] //初始化N，n，初始化tree[]为0 //函数输入，函数返回值输出 static const int N; int n,tree[N]; void ini(int _n){ n=_n; for(int i=1;i<=n;i++)tree[i]=0; }; void add(int k,int d){for(int i=k;i<=n;i+=i&-i)tree[i]+=d;} int sigma(int k){ int ret=0; for(int i=k;i;i-=i&-i)ret+=tree[i]; return ret; } int sigma(int u,int v){return sigma(v)-sigma(u-1);} }; struct Binary_Indexed_Tree{ //区间更新点查询,最大可用范围[1,N）,实际使用[1,n] //初始化N，n初始化tree[]为0 //函数输入，函数返回值输出 static const int N; int n,tree[N]; void ini(int _n){ n=_n; for(int i=1;i<=n;i++)tree[i]=0; }; void add(int k,int d){for(int i=k;i<=n;i+=i&-i)tree[i]+=d;} void add(int u,int v,int d){ add(u,d); add(v+1,-d); } int sigma(int k){ int ret=0; for(int i=k;i;i-=i&-i)ret+=tree[i]; return ret; } }; struct Binary_Indexed_Tree{ //区间更新区间查询,最大可用范围[1,N）,实际使用[1,n] //初始化N，n初始化tree[]、tree2[]为0 //函数输入，函数返回值输出 static const int N; int n,tree[N],tree2[N]; void ini(int _n){ n=_n; for(int i=1;i<=n;i++)tree[i]=0; }; void add(int k,int d){ for(int i=k;i<=n;i+=i&-i)tree[i]+=d,tree2[i]+=k*d; } void add(int u,int v,int d){ add(u,d); add(v+1,-d); } int sigma(int k){ int ret=0; for(int i=k;i;i-=i&-i)ret+=(k+1)*tree[i]-tree2[i]; return ret; } int sigma(int u,int v){ return sigma(v)-sigma(u-1); } }; struct Binary_Indexed_Tree{ //二维点更新区间查询,最大可用范围[1,N)[1,N),实际使用[1,n] //初始化N，n初始化tree[][]为0 //函数参数输入，函数返回值输出 static const int N; int n, tree[N][N]; void ini(int _n){ n=_n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ tree[i][j]=0; } } } void add(int x,int y,int d){ for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=n;j+=j&-j) tree[i][j]+=d; } int sigma(int x,int y){ int ret=0; for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j) ret+=tree[i][j]; return ret; } int sigma(int x1,int y1,int x2,int y2){ if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); x1--;y1--; return sigma(x1,y1)+sigma(x2,y2)-sigma(x1,y2)-sigma(x2,y1); } }; struct Binary_Indexed_Tree{ //二维区间更新点查询,最大可用范围[1,N)[1,N),实际使用[1,n] //初始化N，n初始化tree[][]为0 //函数参数输入，函数返回值输出 static const int N; int n,tree[N][N]; void ini(int _n){ n=_n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ tree[i][j]=0; } } } void add(int x,int y,int d){ for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=n;j+=j&-j) tree[i][j]+=d; } void add(int x1,int y1,int x2,int y2,int d){ if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); add(x1,y1,d); add(x2+1,y2+1,d); add(x1,y2+1,-d); add(x2+1,y1,-d); } int sigma(int x,int y){ int ret=0; for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j) ret+=tree[i][j]; return ret; } }; struct Binary_Indexed_Tree{ //二维区间更新区间查询,最大可用范围[1,N)[1,N),实际使用[1,n] //初始化N，n初始化tree[][]、treeij[][]、treei[][]、treej[][]为0 //函数参数输入，函数返回值输出 static const int N; int n,tree[N][N],treeij[N][N],treei[N][N],treej[N][N]; void ini(int _n){ n=_n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ tree[i][j]=treei[i][j]=treej[i][j]=treeij[i][j]=0; } } } void add(int x,int y,int d){ for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=n;j+=j&-j){ tree[i][j]+=d; treei[i][j]+=x*d; treej[i][j]+=y*d; treeij[i][j]+=x*y*d; } } void add(int x1,int y1,int x2,int y2,int d){ if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); x2++,y2++; add(x1,y1,d); add(x2,y2,d); add(x1,y2,-d); add(x2,y1,-d); } int sigma(int x,int y){ int ret=0; for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j){ ret+=(x+1)*(y+1)*tree[i][j]+treeij[i][j]; ret-=(x+1)*treej[i][j]+(y+1)*treei[i][j]; } return ret; } int sigma(int x1,int y1,int x2,int y2){ if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); x1--,y1--; return sigma(x1,y1)+sigma(x2,y2)-sigma(x2,y1)-sigma(x1,y2); } };
