（算法模板）树状数组

模板题 LC307. 区域和检索 – 数组可修改

树状数组可以在log(N)的时间复杂度内完成数组中单点的修改和任意一段的值求和。

十进制表示

二进制的版本

盗两张别人的图可以更清楚一些。

具体推导过程可以参考之前的笔记或者其他博客的内容，这里不再赘述，主体思想是利用二进制下标的性质来完成对整个数组的划分，分成log(N)段，然后在查询和更新时分别从自顶向下、自底向上进行更新即可。

记住上面的图比什么方法都好使！

关键：树状数组的下标从1开始

// 注意数组的下标，树状数组的下标一定是从1开始的
// 为了统一我们a数组也从下标为1开始

int a[N];       // 保存原始数据
int tr[N];      // 存储树状数组

// lowbit操作：取一个数的最低二进制位
int lowbit(int x) {
    return x & (-x);
}

// 注意下标
// 初始化树状数组
// 使用树状数组的定义进行初始化
// tr[x]为 [x-lowbit(x)+1, x]的和
// 我们可以先初始化前缀和，然后构建树状数组，这样是O(N)
void init() {
    int prefix[N+1];
    for(int i = 1; i<=n; i++) {
        prefix[i] = prefix[i-1] + a[i];
    }
    for(int i = 1; i<=n; i++) {
        tr[i] = prefix[i] - prefix[i-lowbit(i)];
    }
}

// 更新操作：将index位置的值更新成val
// 自底向上进行更新
void update(int index, int val) {
    int delta = val - a[index];
    a[index] = val;
    for(int i = index; i<=len; i += lowbit(i)) {
        tr[i] += delta;
    }
}

// 得到 1~index的总和
// 自顶向下进行求和
int getsum(int index) {
    int ans = 0;
    for(int i = index; i>0; i -= lowbit(i)) {
        ans += tr[i];
    }
    return ans;
}