树状数组

1. 定义

树状数组是一种动态维护数组前缀和、区间和的数据结构。其思想和跳变类似: 添加索引, 高效维护数组。

2. 构建树状数组思路

任意一个正整数可以唯一分解为若干个不重复的2次幂之和。如: 7 = 2^2 + 2^1 + 2^0, 12 = 2^3 + 2^2

基于二进制的思想, C[k]表示的就是k的二进制表示下的最低位的1以及后面的0组成的数的长度。因此c[12] = a[12] + a[11] + a[10] + a[9]。

lowbit(x) 定义为: x二进制下最低位的1和后面的0组成的数值(等价于x 二进制分解下的最小次幂)。

2.1 树状数组的性质

每个内部节点c[x] 保存以它为根的子树中所有叶节点的和。除树根外，每个内部节点c[x] 的父节点是c[x + lowbit(x)]。

2.2 树状数组的查询操作

int query(int x) {  // 查询前缀和(前x个数据的和)
    int ans = 0;
    for(; x > 0; x -= x & -x) ans += c[x];
    return ans;
}  

2.3 树状数组的更新操作

void add(int x, int delta) { // 第 x 个数加上 delta
    for(; x <= N; x += x & -x) c[x] += delta;
}

3. 模板题目

leetcode区域和检索

3.1 代码

class NumArray {
public:
    NumArray(vector<int>& nums) {
        n = nums.size();
        a = vector<int>(n + 1, 0);
        c = vector<int>(n + 1, 0);

        for(int i = 1; i <= n; i++) {
            a[i] = nums[i - 1];
            add(i, nums[i - 1]);
        }
    }
    
    void update(int index, int val) {
        ++index;  // 因为将原数组往后移动了一位
        int delta = val - a[index];
        add(index, delta);
        a[index] = val;
    }
    
    int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }

private:
    int n;
    vector<int> a;  // 原数组
    vector<int> c;  // 树状数组

    int query(int x) {
        int ans = 0;
        for(; x > 0; x -= lowbit(x)) ans += c[x];
        return ans;
    }

    void add(int x, int delta) {
        for(; x <= n; x += lowbit(x)) c[x] += delta;
    }

    int lowbit(int x) {
        return x & -x;
    }
};