树状数组(Binary Indexed Tree)

简介

中文名和英文名分别对应了形象的和原理的两种理解，树状数组是基于二进制的应用，也是简化版的线段树(为了以数组存储，节约空间)，主要用于处理区间和的问题；

查询和修改的时间复杂度都是O(logn)，总空间复杂度为O(n)。(本文参考这篇博客)

原理与做法

下面这张图比较形象：

可以看到树状数组的每一项都对上了原数组，所以空间上一致；结构上正好是前缀和的形式；

但是由于设计原理特性，原数组需要从1开始来看待，这是为了配合计算，规律如下：

可以归纳出通项公式：$c[i]=\Sigma_{j=0}^{2^k-1}{a[i-j]}$，k即取二进制数最低位连续0长度(别推了，倒推这个本来就不实际)；实际使用中直接算出$2^k$的值，即lowbit(i)函数：
```
 int lowbit(int x){
     return x&(-x); //利用补码特性
     // return x&(x^(x-1)); //这是纯数学做法
 }
```
使用上分为初始化、添加(更新)以及查询三种操作；
- 初始化：有两种方案，一是直接用添加的方法逐个加入元素，这样时间复杂度是O(nlogn)，但空间复杂度是O(n)；二是在初始状态上维护一个前缀和数组，再根据通项直接赋值，这样的时间复杂度是O(n)，但需要O(2n)的空间，优点是当初始数组比较有规律时，可以直接算出前缀和通项，就无须建数组；
- 添加/更新：更新c[i]之后还要更新后续节点，代码在下面；
- 查询：和更新反向的操作，代码如下；

// c[i] += k;
void update(int i, int k){ 
    while (i <= n){
        c[i] += k;
        i += lowbit(i);
    }   
}

// a[1]+a[2]+...+a[i];
void getsum(int i){ 
    int res = 0;
    while (i > 0){
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}