树状数组

yyycj · 2025-09-28 22:58:08 · 算法·理论

树状数组可用于动态查询数组的前缀和，其支持单点修改、区间修改、单点查询、区间查询操作。

树状数组的根本思想其实是分块，把每个区间分成最多 \log n 个区间，这样查询的复杂度即 \log n。

我们可以这样分块，观察 10 这个数，(10)_{10}=(1010)_{2}，那么我们就可以将树状数组的第 10 个数看做树状数组的第 10 个数和第 8 个数的和，我们可以发现这分别是 10 的二进制不减去任何数和减去最低位 1 的权值的数。按照此规律，每个数都这么算，最终就能得到一个树状数组。具体地：

其中 a 表示原数组，c 表示树状数组。

那么我们如何得到这个数的二进制中 1 的权值呢？这就是树状数组的核心操作 \operatorname{lowbit}(x)，它表示 x 中最低位 1 的权值，有了它我们只需每次先使答案增加 c_{x}，然后 x \gets x-\operatorname{lowbit}(x)，直到 x 为 0。这就是 query 操作。

而对于单点修改，其实就是区间查询的逆运算，不难发现只要每次先 c_{x} \gets c_{x}+k，然后 x \gets x +\operatorname{lowbit}(x) 即可。这就是 update 操作。

然后对于区间修改，我们可以对树状数组进行差分，这样就可以进行单点查询。如果要区间修改与区间查询，可使用线段树。

Code

long long a[N], sum[N];
// ----------------------------
int lowbit(int x) {
    return (x & -x);
}

long long query(int x) {
    long long res = 0;
    while (x) {
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}

void update(int x, int k, int n) {
    while (x <= n) {
        sum[x] += k;
        x += lowbit(x);
    }
}
// ----------------------------
int n, m; read(n, m);
for (int i = 1; i <= n; i++) {
    read(a[i]);
    update(i, a[i], n);
}
// ----------------------------
int op, x, k, y;
while (m--) {
    read(op);
    if (op == 1) {
        read(x, k);
        update(x, k, n);
    }
    else {
        read(x, y);
        print(query(y) - query(x - 1));
        putchar('\n');
    }
}