用于数组区间求和，相比于前缀和的方式，树状数组的优点是能有效应对单点修改。
树状数组区间求和以及单点修改的时间复杂度都是O(logn)，而前缀和虽然区间求和时间复杂度为O(1)，但更新一个元素后需要重新计算前缀和，时间复杂度为O(n)，如果需要频繁更新数组元素，则效率不如树状数组。
树状数组的思想是将区间分成大小不同，相互包含的一些节点，在区间求和或单点修改时，只需要查询或更新较大的节点，而不需要处理较小的节点。
以下是一个树状数组的示例：
原数组是a1~a8，数组状数组是c1~c8，它们拥有的元素个数完全一样，并且都从下标1开始存储元素。
分析树数组和原数组的关系，列出对应的二进制：
| 树状数组节点下标 | 节点下标的二进制 | 对应原数组节点范围 | 最后一个元素下标 | 元素个数 |
|---|---|---|---|---|
| 1 | 0001 | 1 | 1 | 1 |
| 2 | 0010 | 1~2 | 2 | 2 |
| 3 | 0011 | 3 | 3 | 1 |
| 4 | 0100 | 1~4 | 4 | 4 |
| 5 | 0101 | 5 | 5 | 1 |
| 6 | 0110 | 5~6 | 6 | 2 |
| 7 | 0111 | 7 | 7 | 1 |
| 8 | 1000 | 1~8 | 8 | 8 |
这里首先介绍如何推导出cx管理的元素个数，推导公式如下：
int lowbit(int x) {
return x & -x;
} |
这个公式可以返回x的二进制右侧第一个非0的部分，比如：0001，0010，0011，0100，0101，0110，0111，1000。
lowbit(x)的求法是x各位取反再加1，再与x本身进行与操作，比如i=20，其二进制表示为10100，取反之后为01011，加1之后为01100，再与20本身进行与操作，结果为01100&10100，得到结果为100。
而x各位取反再加1，刚好就是-x的补码表示，所以lowbit(x) = x & -x。 |
推导出元素个数后，就可以知道cx管理的元素范围为[x-lowbit(x)+1, x]。，比如c8管理的元素范围是[1, 8]。
根据上面的二进制关系，同样可以推导出原数组元素ax归哪些树状数组节点管理，比如从上面的例子可知，a1归c1, c2, c4, c8管理，那么在更新a1的值时，就要同步更新c1, c2, c4, c8 的值。
假设节点数为n，则更新节点ak的过程如下：
void update(int k, int val) {
for(int i = k; i <= n; i += lowbit(i); { // 推导a[k]归哪些c[i]管理
c[i] += val;
}
} |
代入上面的表格进行验证即可。
接下来是求前缀和，假设要求区间[1, x]的和，那么倒着上面的计算公式进行求解即可：
int getsum(int x) {
int ans = 0;
while(x >= 1) {
ans += c[x];
x -= lowbit(x);
}
return ans;
} |
同样代入上面的表格进行验证即可。
最后是如何建立树状数组，示例代码如下，这里在每确定一个c[i]时，都会更新一次c[i]的直接父结点，由于父结点的值只来自于子结点求和，所以建树的时间复杂度为O(n)：
#define MAXN 1005
int a[MAXN];
int c[MAXN];
int n;
void init() {
for(int i = 1; i <= n; i++) {
c[i] += a[i];
int j = i + lowbit(i);
if(j <= n) c[j] += c[i];
}
} |
示例例题：
