树状数组又称二叉索引树(Binary Indexed Tree)，1994年由Fenwick发明。多用于高效计算数列的前缀和， 区间和。可以以\(O(log n)\)的时间得到任意前缀和，并且可以在\(O(log n)\)时间内修改单点的值。其空间复杂度是\(O(n)\)。
思想
我们有一个数组 A，对它进行如下构造，构造出一个如下的树状数组 C。
其中C[i]等于与它连线的元素相加：
C1 = A1；
C2 = A1+A2；
C3 = A3；
C4 = A1+A2+A3+A4；
......
我们定义一个函数 lowbit(i) ：表示二进制数 i 的低位第一个非零1代表的数。如 2(0010) 的 lowbit 为 \(10_{2}\)；3(0011) 的 lowbit 为 \(1_{2}\)；8(1000) 的 lowbit 为 \(1000_{2}\)。
我们可以发现，C[i] 是由一些连续的A[i]、A[i-1]、A[i-2]...相加得来的。具体是多少个连续的A[j]相加呢，就是数组C的下标的lowbit个，比如：C2 = A1+A2，C2的lowbit是2；C3 = A3，C3的lowbit是1； C4 = A1+...+A4，C4的lowbit是4。因此可以得到如下的关系式：
\[C[i] = \sum_{j=i-lowbit(i)+1}^{i}{A[j]} \]有了关系式我们就可以构造出树状数组C了。
这样在求前缀和S[i]时，我们不用去求A[1]+...+A[i]，而是可以通过数组C来求。
比如求S[4]，即是C[4]；S[6] = C[6] + C[4]；S[8] = C[8]。可以看到，这大大降低了求前缀和的复杂度。
树状数组的思想就是：所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。采用这个想法，我们可将一个前缀和划分成多个子序列的和，而划分的方法与二分非常相似。
基本方法
变量说明：原数组 A，树状数组 BIT
注意，通常我们会让 A[0]、BIT[0]都为空，从下标1开始存放数据，这会让编程更方便。因此下面给出的方法都是这样假定的。具体使用时你可以根据需要做一些小心的下标变换，改成从下标0开始
lowbit
在计算机中计算 lowbit 有非常高效的位运算：lowbit(x) = x & -x
int lowbit(int x){
return x&(-x);
}
初始化 BIT
void init(){
for (int i = 1; i <= A.length; i++) {
BIT[i] = A[i];
for (int j = i - 1; j > i - lowbit(i); j -= lowbit(j)){
BIT[i] += BIT[j];
}
}
}
单点修改
// 将A[i]的值增加 delta
void add(int i,int delta){
for(int j=i; j<=A.length; j+=lowbit(j))
BIT[j] += delta;
}
求前缀和
// 求下标 k 的前缀和
int sum(int k){
int ans=0;
for(int i=k; i>0; i-=lowbit(i))
ans+=BIT[i];
return ans;
}