版权声明：“树状数组简介”中所用插图出自这里。链接到的是转载博文，转载作者未链接原文。侵删。其余讲解部分为本人原创。
1.例题（HDU1166）
题意：给出一个序列，有如下操作：为其某子区间中的所有数价钱相同值，查询其某子区间内所有值的和。要求在查询操作后输出所求的和。
2.分析引入
乍看之下，这道题直接用for循环在指定区间内逐个求和。然而，必须注意这道题数据量给的非常大，直接使用for循环必定超时。那么，有没有一种方法，能降低序列求和的复杂度呢？或者更具体来说，正常的求和是逐个相加，对长为n需要进行n次加和操作，时间复杂度O(n)那么，有没有方法能使这种操作次数降低到n以下，时间复杂度达到O(logn)级别？这时，就需要引入树状数组这一数据结构了。
3.树状数组简介
对于一个常规数组a[]存储一个序列，a[i]表示的是序列中位置为i的元素的值。而对于一个树状数组c[]存储一个序列，c[i]表示的是序列中某一个以i为右界的子区间存储的值。那么这个区间具体会包含那些元素呢？
先回到树状数组本身，为什么会被称作树状数组？因为树状数组是基于二叉树的，如图是一个二叉树，令其叶子节点代表常规数组a[]中的a[1]到a[8]：
然后对二叉树做出以下变形：
可以发现，这个二叉树可以分为8列，这时，我们使用一个数组c[]表示每一列的最高点，并且使该二叉树根节点的值为其左右孩子节点的值之和。如图所示：
这里的c[]就是我们所说的树状数组。比如c[1] = a[1]，c[4] = c[2] + c[3] + a[4] = a[1] + a[2] + a[3] a[4],换一种写法，a[1] + a[2] + ... + a[7] = c[4] + c[6] + c[7]这里我们就可以发现，原先的7个数加和，变为了现在的3个数加和，复杂度得到了有效的降低。
那么该如何判断所求区间中元素综合具体是树状数组中哪几位的和？可以通过二进制来寻找规律：
1 = (001) c[1] = a[1]
2 = (010) c[2] = a[2] + a[1]
3 = (011) c[3] = a[3]
4 = (100) c[4] = a[4] + a[3] + a[2] + a[1]
6 = (110) c[6] = a[6] + a[5]
7 = (111) c[7] = a[7]
可以发现，c[i] = c[i] + c[i - 1] + ... + c[i - n + 1]其中，n为i在二进制中最低位1在十进制中的值。比如(010)，最低位1在第二位，在十进制中为2，(100)最低位1在第三位，在十进制中为4，那么如何求解n呢？这里引入lowbit。（见下一板块）
3.树状数组的基本操作
- lowbit
如何求解n？(n的意义见上文)求解n，需要“消除”所有比最高为1高的数，而且，在“消除”的同时，得要保证最高位1以及其后面的0不受影响，如何实现？
这里想到使用补码。i的补码就是i的反码加一，比如22 = (10110)，它的反码是(01001)，它的补码是(01010)，这时，将13的补码与13进行按位与，得到(00010) = 4，由此可见，比最低位1高位的数被“消除”，而最低为1以及其后的0被保护了，得到的4就是n。求和为c[i]的元素个数为lowbit(i)。以上，就是lowbit过程。根据一个数的负数在二进制中式这个数的补码的性质，可利用以下方法进行lowbit操作：
int lowbit(int x)
{
return x & (-x);
}- 对某一区间内所有数求和
树状数组的优点就体现在其低复杂度的求和操作。一个区间的和，可以视为从位置1开始到所求区间左界前一位与右界的两区间之差。即：
a[l] + a[l + 1] + ... + a[r] = a[0] + a[1] + ... + a[r] - (a[0] + a[1] + ... + a[l - 1])
然后要解决的，是对两区间的求和操作。为了描述方便，下面采用sum(x)表示a[1] + a[2] + ... + a[x]。
假设现在要求解sum(7)，根据上文，sum(7) = c[7] + sum(6)，这时需要求解sum(6)，而sum(6) = c[6] + sum(4)，sum(4) = c[4]，于是sum(7) = c[7] + c[6] + c[4]，而上文说到，求和为c[i]的元素个数为lowbit(i)，于是，求和就很好实现了。
int query(int pos)
{
int sum = 0;
for(int i = pos;i > 0;i -= lowbit(i))
sum += c[i];
return sum;
}
int sum(int l, int r)
{
return query(r) - query(l);
}- 改变一个元素的值
按照树状数组的性质，改变第i个元素的值，改变的显然是c[i]以及其后的值，因为c[i]存储的是第i - lowbit(i) + 1到第i位的值。还是由于求和为c[i]的元素个数为lowbit(i)，可以按以下方法实现：（很多教程说这是求和的逆过程，本人不完全赞同，因为起点是不一样的，但是所用的原理是相同的）
void update(int pos,int x)
{
for(int i = pos;i <= n;i += lowbit(i)) //n为序列所含元素个数
c[i] += x;
}4.例题（HDU1166）AC代码
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;
const int maxn = 5e4+5;
int c[maxn];
int n,T,tmp;
char s[20];
int lowbit(int x)
{
return x & (-x);
}
void update(int pos,int x)
{
for(int i = pos;i <= n;i += lowbit(i))
c[i] += x;
}
int query(int pos)
{
int sum = 0;
for(int i = pos;i > 0;i -= lowbit(i))
sum += c[i];
return sum;
}
// int sum(int l, int r)
// {
// return query(r) - query(l);
// }
int main()
{
scanf("%d", &T);
for(int t = 1;t <= T;++t)
{
scanf("%d", &n);
memset(c,0,sizeof(c));
for(int i = 1;i <= n;++i)
{
scanf("%d", &tmp);
update(i,tmp);
}
printf("Case %d:\n", t);
while(true)
{
scanf("%s", s);
if(s[0] == 'Q')
{
int l,r;
scanf("%d%d", &l, &r);
printf("%d\n", query(r) - query(l - 1));
}
if(s[0] == 'A')
{
int pos,x;
scanf("%d%d", &pos, &x);
update(pos,x);
}
if(s[0] == 'S')
{
int pos,x;
scanf("%d%d", &pos, &x);
update(pos,-x);
}
if(s[0] == 'E')
break;
}
}
return 0;
}
ACM暑假学习与复习笔记：传送门
