请点击这个链接：树状数组(Markdown版本)_xiji333的博客-CSDN博客。
树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。
最经典的应用就是查询某一段区间元素的和，而且支持在线修改操作。如果没有修改操作，就没必要用树状数组了。
实际上树状数组就是没有右儿子的线段树，它实现起来比线段树简单，而且效率更高，空间占用的也更少。但是能用树状数组解决的问题，基本上都能用线段树解决。(反过来就不是了)
不多解释了，先上几张图：
我们用数组A表示原序列：A1、A2……An
用数组C代表树状数组，从上图中我们可以发现：
C1=A1 C2=A1+A2 C3=A3 C4=A1+A2+A3+A4 C5=A5 C6=A5+A6 C7=A7 C8=A1+A2+A3+A4+A5+A6+A7+A8
对应数组C下标的二进制表示：
C1的下标1的二进制表示 1 末尾有0个连续的0 该节点管理1个元素
C2的下标2的二进制表示 10 末尾有1个连续的0 该节点管理2个元素
C3的下标3的二进制表示 11 末尾有0个连续的0 该节点管理1个元素
C4的下标4的二进制表示 100 末尾有2个连续的0 该节点管理4个元素
……
由此我们得到一个规律：我们设i的二进制表示的末尾有k个连续的0，那么Ci管理2^k个元素。那么有什么办法可以很快的算出来2^k呢？我们有一个名为lowbit的神奇操作：x&(-x) 就是我们想要的答案。且对于节点i，i+lowbit(i)就是节点i的父节点。
我们可以对照上图，若我们求[1，7]的区间和，那么sum=C7+C6+C4，即三次操作就得到了我们想要的结果，这也是为什么查询的复杂度是O(lgn)的，那么我们看看lowbit发挥了怎样的作用吧：7-lowbit(7)=6 6-lowbit(6)=4 4-lowbit(4)=0。可以发现，我们求和的操作就是从区间右端点r开始，不断地累加Cr，同时对r作lowbit操作。那么修改操作呢，就逆着来，即从要开始的子节点i开始，不断修改Ci，同时对i做lowbit操作。有人可能会问，你这求的是[1，r]的和啊，我要求[l，r]的和怎么办呢？很简单，把[1，r]和[1，l-1]的和均求出来，然后用前者减去后者即可得到答案。
这里我以求某段区间和作为例题来介绍一下线段树的基本操作。(注意 树状数组的下标是从1开始的)
lowbit操作：
inline int lowbit(int x)
{
return x&(-x);
}更新操作：(单点修改)
void update(int i,int v)
{
for(;i<=n;i+=lowbit(i))
tree[i]+=v;
}查询操作：
int sum(int l)
{
int s=0;
for(;l;l-=lowbit(l))
s+=tree[l];
return s;
}一位树状数组的内容就到这里了~大家可以做题体会一下~
举一个简单的例子，我们有16个元素：A1、A2、A3、A4、……A16构成了一个4*4的矩阵，我想查询某个矩阵内所有元素的和，并且可能会修改该矩阵的某个元素怎么做呢？朴素算法肯定是遍历统计和，复杂度O(n^2)，那有没有O((lgn)^2)的算法呢？肯定有，这就是我们要介绍的二维数组，首先要知道对于Tree[i][j]的每一个Tree[i]肯定是一个一维的树状数组，但是其存储的东西可能跟你想的有点区别：(并不是简简单单的Tree[1]管理A1-A4 Tree[2]管理A5-A8哦)
我们先写出四个一维的树状数组：
tree1[1]=A1 tree1[2]=A1+A2 tree1[3]=A3 tree1[4]=A1+A2+A3+A4
tree2[1]=A5 tree2[2]=A5+A6 tree2[3]=A7 tree2[4]=A5+A6+A7+A8
tree3[1]=A9 tree3[2]=A9+A10 tree3[3]=A11 tree3[4]=A9+A10+A11+A12
……
然后再写出我们的二维树状数组：
Tree[1][1]=A1 Tree[1][2]=A1+A2 Tree[1][3]=A3 Tree[1][4]=A1+A2+A3+A4
Tree[2][1]=A1+A5 Tree[2][2]=A1+A2+A5+A6 Tree[2][3]=A3+A7 Tree[2][4]=A1+A2+A3+A4+A5+A6+A7+A8
Tree[3][1]=A9 Tree[3][2]=A9+10 Tree[3][3]=A11 Tree[3][4]=A9+A10+A11+A12
……
也就是说Tree[i]维护的是：treei+tree(i-1)+……+tree(i-lowbit(i)+1) 比如上面Tree[2]维护的就是tree2和tree1
那么我们求这个矩阵从第1行到第x行，第1列到第y列的操作就很简单了：(就是原来的一维变成了二维)
至于怎么求中间的某个矩阵的和就留给大家思考了~
void add(int x,int y,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
tree[i][j]+=v;
}
int query(int x,int y)
{
int sum=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
sum+=tree[i][j];
return sum;
}树状数组处理RMQ问题：
修改：
void updata(int x)
{
int lx,i;
while x<=n)
{
h[x]=a[x];
lx=lowbit(x);
for(i=1;i<lx;i<<=1)
h[x]=max(h[x],h[x-i]);
x+=lowbit(x);
}
}查询：
int query(int x,int y)
{
int ans=0;
while(y>=x)
{
ans=max(a[y],ans);
y--;
for(;y-lowbit(y)>=x;y-=lowbit(y))
ans=max(h[y],ans);
}
return ans;
}针对区间[1，r]的查询：
int query(int r)//查询[1,r]
{
int ans=INF;
while(r)
{
ans=min(ans,tree[r]);
r-=lowbit(r);
}
return ans;
}