树状数组

Posted on 2022-08-21 Edited on 2022-09-07 Symbols count in article: 1.7k Reading time ≈ 2 mins.

需求

随机修改数组中一个数字
求前缀和
以上操作需要频繁操作

预备知识：lowbit

lowbit 指数字的二进制最低位 1 及后续 0 取出后的数字

1
2
3

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

例如：10：1010 & 0110 = 0010，即 10 的 lowbit 为 2。

x	1	2	3	4	5	6	7	8	9	10
lowbit(x)	1	2	1	4	1	2	1	8	1	2

注意：0 不存在 lowbit，所以数组的下标需要右偏移一位（使用时偏移或初始化多 1 位）

树状数组

tarr 从 1 开始，arr 从 0 开始
树状数组的每一个元素 tarr[i]：其值为 a[j]+...a[i-1]+a[i-1]，其中连加的项总共 lowbit(i) 个
在树状数组中，为什么需要寻找其父节点？有两个用处：1、初始化树状数组。2、修改某个数同时修改其祖上一系列树状数组的值。对于 tarr[i] 而言，其直接父节点即为 tarr[i + lowbit(i)]，通过这种方式逐步向上迭代，即可探寻祖上一条链
对于给定数组：arr = [1,3,2,6,4,1]，可得其对应的树状数组：tarr = [1, 1+3, 2, 1+3+2+6, 4, 4+1] -> [1, 4, 2, 12, 4, 5]
求和时，例如 sum(idx=13)
- 先得到 res += tarr[13]，随后 idx -= lowbit(idx)，此时 idx==12
- 再得到 res += tarr[12]，随后 idx -= lowbit(12)，此时 idx==8
- 再得到 res += tarr[8]，随后 idx -= lowbit(8)，此时 idx==0 结束循环
- 最终，res = tarr[13] + tarr[12] + tarr[8] = (arr[12]) + (arr[8]+...+arr[11]) + (arr[0]+...+arr[7])
总之，对于树状数组 tarr
- idx += lowbit(idx) 是为了寻找祖上，修改和初始化用到
- idx -= lowbit(idx) 是为了求和

代码

class TreeArr {
public:
    TreeArr(vector<int> arr) :arr(arr), tarr(arr.size()+1) {
        // 初始化树状数组，arr中的每个元素被加到其祖上所有节点中
        for (size_t i = 0; i < arr.size(); ++i) {
            size_t idx = i + 1; // 偏移1位
            while (idx < tarr.size()) {
                tarr[idx] += arr[i];
                idx += lowbit(idx);
            }
        }
    }

    void update(int i, int val) {
        int diff = val - arr[i];
        size_t idx = i + 1;
        // 修改时也要修改其祖上所有节点 + lowbit(idx)
        while (idx < tarr.size()) {
            tarr[idx] += diff;
            idx += lowbit(idx);
        }
        arr[i] = val; // 勿忘
    }

    int getSum(int i) {
        int idx = i + 1;
        int res = 0;
        // 求和时则是 - lowbit(idx)
        while (idx > 0) {
            res += tarr[idx];
            idx -= lowbit(idx);
        }
        return res;
    }

    int getRange(int l, int r) {
        return getSum(r) - getSum(l - 1); //!
    }


    static int lowbit(int a) {
        return a & -a;
    }
private:
    vector<int> arr;
    vector<int> tarr;
};

需求

预备知识：lowbit

树状数组

代码

参考