树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。特别用于在数组内的参数变换后，再次求和所使用的时间复杂度减少问题。
下面是一道水题：POJ上的stars，题目大意为：按照纵坐标y从小到大的顺序依次输入几个星星的横纵坐标，横纵坐标小于等于该星星的星星数量即为该星星的等级，求每个等级的星星数量。
由于输入的顺序是按照纵坐标从小到大的顺序（y相同时x的坐标也是由小到大输出），那么一个星星的满足条件的星星一定在输入的这个星星的前方，故在这道题中，y坐标是没有用处的，我们可以每次输入一个x值，就判断之前输入过的数中，小于x的星星的个数，例如：输入坐标：
5 1
1 2
2 2
3 2
那么第三个数据之前有第二和第三两个符合条件（横坐标是1，2都小于5），所以第三颗星星的等级是2，但是如果按照这种方法逐个统计的话，在星星的数量达到一定数量时，遍历一次并且每个都判断一次的话，是一定超时的，所以，可以想到，开辟一个数组ar，下标1：ar[1]代表的是在输入到当前时，横坐标为1的个数，ar[2]即是横坐标为2的星星的个数，依次类推，加入当前输入的横坐标是4，那么结果就是ar[0]+ar[1]+ar[2]+ar[3]+arr[4]（纵坐标按顺序输入，那么则表明已经输出的星星纵坐标一定小于等于当前纵坐标，只要横坐标满足条件则整体一定满足），结果保留，并将ar[4]++。
但是，如果当前输入的横坐标n达到了数万位，那么还要继续从ar[0]遍历求和到ar[n]吗？当然是行不通的，所以，又需要将该模型进行优化。
我们的方法是：如果每间隔一段距离，一个arr数空间存放的就是前面的一段数组的和是不是会简便很多？那样就不需要每次都使用遍历所有的节点来求和了，至少会遍历较少的数，那么，这就涉及到了树状数组，不妨回忆一下二叉树的原型，最上面一个根结点，下面每个节点都展开分支，我们假设每个叶子节点代表ar[i]，他们的根结点来记录和，那么整棵树的根节点就是和了，想想是不是方便了很多？
如果当前横坐标是3，那么只要输出C的值，这样减少了很多遍历的时间，但是同时存在的问题是，如果当前横坐标是0的话，还可以输出ar[0]，一的话输出A，那么如果2的话呢？输出的又该怎么处理呢？还有应该怎样在输出的时候顺利得找到A，或C点呢？树状数组的处理将会解决这些问题：
下面是从网上转载的一些关于树状数组的详细推断，以二进制的形式方便的找到每一个范围内的非叶子节点：
假设树状数组C[]，序列为A[1]~A[8]
网络上面都有这个图，但是我将这个图做了2点改进。
（1）图中有一棵满二叉树，满二叉树的每一个结点对应A[]中的一个元素。
（2）C[i]为A[i]对应的那一列的最高的节点。
那么C[]如何求得？
C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
以上只是枚举了所有的情况，那么推广到一般情况，得到一个C[i]的抽象定义：
因为A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把A[]中的每个元素当成叶子，那么：C[i]=C[i]的所有叶子的和。
把具体的数标上不知道有没有好点
现在不得不引出关于二进制的一个规律：
先仔细看下图：
将十进制化成二进制，然后观察这些二进制数最右边1的位置：
1 --> 00000001
2 --> 00000010
3 --> 00000011
4 --> 00000100
5 --> 00000101
6 --> 00000110
7 --> 00000111
8 --> 00001000
1的位置其实从我画的满二叉树中就可以看出来。但是这与C[]有什么关系呢？
接下来的这部分内容很重要：
在满二叉树中，
以1结尾的那些结点（C[1],C[3],C[5],C[7]），其叶子数有1个，所以这些结点C[i]代表区间范围为1的元素和；
以10结尾的那些结点（C[2],C[6]），其叶子数为2个，所以这些结点C[i]代表区间范围为2的元素和；
以100结尾的那些结点（C[4]），其叶子数为4个，所以这些结点C[i]代表区间范围为4的元素和；
以1000结尾的那些结点（C[8]），其叶子数为8个，所以这些结点C[i]代表区间范围为8的元素和。
扩展到一般情况：
i的二进制中的从右往左数有连续的x个“0”，那么拥有2x个叶子，为序列A[]中的第i-2x+1到第i个元素的和。
终于，我们得到了一个C[i]的具体定义：
C[i]=A[i-2^x+1]+…+A[i]，其中x为i的二进制中的从右往左数有连续“0”的个数。
利用树状数组求前i个元素的和S[i]
理解了C[i]后，前i个元素的和S[i]就很容易实现。
从C[i]的定义出发：
C[i]=A[i-2^x+1]+…+A[i]，其中x为i的二进制中的从右往左数有连续“0”的个数。
我们可以知道：C[i]是肯定包括A[i]的，那么：
S[i]=C[i]+C[i-2^x]+…
也许上面这个公式太抽象了，因为有省略号，我们拿一个具体的实例来看：
S[7]=C[7]+C[6]+C[4]
因为C[7]=A[7]，C[6]=A[6]+A[5]，C[4]=A[4]+A[3]+A[2]+A[1]，所以S[7]=C[7]+C[6]+C[4]
（1）i=7，求得x=0，那么我们求得了A[7]；
（2）i=i-2^x=6，求得x=1，那么求得了A[6]+A[5]；
（3）i=i-2^x=4，求得x=2，那么求得了A[4]+A[3]+A[2]+A[1]。
也就是说，每个C[i]所存放的是2^x个数据的和，或者说，每个C[i]内和的下标在 i~i-2x+1，下一个C[i-1]的第一个数为i-2x，C[i-1]=C[i-2x]，将i=i-2x，不断递归，结果则为总的和。
讲到这里其实有点难度，因为S[i]的求法，如果要讲清楚，那么得写太多的东西了。所以不理解的同学，再反复多看几遍。
从（1）（2）（3）这3步可以知道，求S[i]就是一个累加的过程，如果将2^x求出来了，那么这个过程用C++实现就没什么难度。
现在直接告诉你结论：2^x=i&(-i)
证明：设A’为A的二进制反码，i的二进制表示成A1B，其中A不管，B为全0序列。那么-i=A’0B’+1。由于B为全0序列，那么B’就是全1序列，所以-i=A’1B，所以：
i&(-i)= A1B& A’1B=1B，即2^x的值。
所以根据（1）（2）（3）的过程我们可以写出如下的函数：
int Sum(int i) //返回前i个元素和
{
int s=0;
while(i>0)
{
s+=C[i];
i-=i&(-i);
}
return s;
}
更新C[]
当有星星不断输入，那么A的数目也会随之改变，所以，如果数组A[i]被更新了怎么办？那么如何改动C[]？
如果改动C[]也需要O(n)的时间复杂度，那么树状数组就没有任何优势。所以树状数组在改动C[]上面的时间效率为O(logn)，为什么呢？
因为改动A[i]只需要改动部分的C[]。这一点从图中就可以看出来：
如上图：
假如A[3]=3，接着A[3]+=1，那么哪些C[]需要改变呢？
答案从图中就可以得出：C[3],C[4],C[8]。因为这些值和A[3]是有联系的，他们用树的关系描述就是：C[3],C[4],C[8]是A[3]的祖先。
那么怎么知道那些C[]需要变化呢？
我们来看“A”这个结点。这个“A”结点非常的重要，因为他体现了一个关系：A的叶子数为C[3]的2倍。因为“A”的左子树和右子树的叶子数是相同的。 因为2x代表的就是叶子数，所以C[3]的父亲是A，A的父亲是C[i+20]，即C[3]改变，那么C[3+2^0]也改变。
我们再来看看“B”这个结点。B结点的叶子数为2倍的C[6]的叶子数。所以B和C[6+21]在同一列，所以C[6]改变，C[6+21]也改变。
推广到一般情况就是：
如果A[i]发生改变，那么C[i]发生改变，C[i]的父亲C[i+2^x]也发生改变。
这一行的迭代过程，我们可以写出当A[i]发生改变时，C[]的更新函数为：
void Update(int i,int value) //A[i]的改变值为value
{
while(i<=n)
{
C[i]+=value;
i+=i&(-i);
}
}
经过以上推断，我们便可以据此得到该题的具体代码实现了：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <string.h>
#define lowbit(x) (x&(-x))
#define MMAX 15005
#define NMAX 32005
using namespace std;
int C[NMAX];
int sum(int i)
{
int ans=0;
while (i>0)
{
ans+=C[i];
i-=lowbit(i);
}
}
void add(int num,int i)
{
while (i<=NMAX)
{
C[i]+=num;
i+=lowbit(i);
}
}
void main()
{
int arr[MMAX]={0};
int i,j,k,n,m,x,y;
scanf("%d",&n);
m=n;
while (n--)
{
scanf("%d%d",&x,&y);
arr[sum(++x)]++;
add(1,x);
}
for (i=0;i<=m;i++)
printf("%d\n",arr[i]);
}
以上是一维树状数组的详解，关于二维的树状数组，则与一维的相似，主要在于元素数组为一个二维的Ａ［ｉ］［ｊ］，相对应的是，树状数组同样对应的一个二维数组Ｃ［ｉ］［ｊ］，不同的是C[i][j]代表的是0到i行和0到j列的和。
下面是在网络上找到的相关注解：
一维树状数组很容易扩展到二维，在二维情况下:
数组A[][]的树状数组定义为：
C[x][y] = ∑ a[i][j], 其中，
x-lowbit(x) + 1 <= i <= x,
y-lowbit(y) + 1 <= j <= y.
例：举个例子来看看C[][]的组成。
设原始二维数组为：A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19},
{a21,a22,a23,a24,a25,a26,a27,a28,a29},
{a31,a32,a33,a34,a35,a36,a37,a38,a39},
{a41,a42,a43,a44,a45,a46,a47,a48,a49}};
那么它对应的二维树状数组C[][]呢？
记: B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...}
这是第一行的一维树状数组
B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...}
这是第二行的一维树状数组
B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...}
这是第三行的一维树状数组
B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...}
这是第四行的一维树状数组
那么：
C[1][1]=a11,C[1][2]=a11+a12,C[1][3]=a13,C[1][4]=a11+a12+a13+a14,c[1][5]=a15,C[1][6]=a15+a1
6,...
这是A[][]第一行的一维树状数组
C[2][1]=a11+a21,C[2][2]=a11+a12+a21+a22,C[2][3]=a13+a23,C[2][4]=a11+a12+a13+a14+a21+a2
2+a23+a24,
C[2][5]=a15+a25,C[2][6]=a15+a16+a25+a26,...
这是A[][]数组第一行与第二行相加后的树状数组
C[3][1]=a31,C[3][2]=a31+a32,C[3][3]=a33,C[3][4]=a31+a32+a33+a34,C[3][5]=a35,C[3][6]=a35+a3 6,...
这是A[][]第三行的一维树状数组
C[4][1]=a11+a21+a31+a41,C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42,C[4][3]=a13+a23+a33+a43,...
这是A[][]数组第一行+第二行+第三行+第四行后的树状数组
搞清楚了二维树状数组C[][]的规律了吗？
仔细研究一下,会发现：
（1）在二维情况下，如果修改了A[i][j]=delta,
则对应的二维树状数组更新函数为：
private void Modify(int i, int j, int delta){
A[i][j]+=delta;
for(int x = i; x< A.length; x += lowbit(x))
for(int y = j; y <A[i].length; y += lowbit(y)){
C[x][y] += delta; } }
（2）在二维情况下，求子矩阵元素之和∑ a[i]j的函数为
int Sum(int i, int j){
int result = 0;
for(int x = i; x > 0; x -= lowbit(x)) {
for(int y = j; y > 0; y -= lowbit(y)) {
result += C[x][y]; } }
return result; }
比如：
Sun(1,1)=C[1][1]; Sun(1,2)=C[1][2]; Sun(1,3)=C[1][3]+C[1][2];...
Sun(2,1)=C[2][1]; Sun(2,2)=C[2][2]; Sun(2,3)=C[2][3]+C[2][2];...
Sun(3,1)=C[3][1]+C[2][1]; Sun(3,2)=C[3][2]+C[2][2];
网友评论