树状数组

引入 链接到标题

数装数组是一种支持单点修改和区间查询的数据结构。

这里的区间查询一般指求和。

普通树状数组维护的信息以及运算要满足结合律并且可以差分。

定义 链接到标题

考虑下标从 $1$ 开始的数组 $a[1]\sim a[8]$，如下图所示：

我们可以发现：

• $c[2]$ 管辖 $\sum\limits_{i = 1}^2 a[i]$；
• $c[4]$ 管辖 $\sum\limits_{i = 1}^4 a[i]$；
• $c[6]$ 管辖 $\sum\limits_{i = 5}^6 a[i]$；
• $c[8]$ 管辖 $\sum\limits_{i = 1}^8 a[i]$；

即 $c[x]$ 管辖 $\sum\limits_{i = x - (x \text{AND} -x) + 1}^x a[i]$。例如 $6\text{AND}(-6) + 1 = 5$。

同时我们定义 $\text{lowbit}(x) = x \text{AND} -x$

使用 链接到标题

那么如何使用树状数组呢，第一步是初始化，我们先假定原数组也是下标从 $1$ 开始，从 $0$ 开始那么做相应变换即可。

初始化 链接到标题

我们先令 $c[i] = 0$，然后遍历 $a[j]$，每次遍历相当于是（假设原数组元素均为 $0$，然后将其值加上 $a[i]$），即初始化树状数组相当于是做了 $n$ 次单点修改。

void build(vector<int> &a, vector<int> &c) {
    for (int i = 1; i < a.size(); ++i) {
        update(i, c, a[i]);
    }
}

单点修改 链接到标题

每次修改 $i$ 处的值，只会影响到 $i$ 以及 $t = i + \text{lowbit}(i)$，并令 $i = t$，如此循环。

int lowbit(int x) {
    return x & (-x);
}
void update(int idx, vector<int> &c, int val) {
    while (idx < c.size()) {
        c[idx] += val;
        idx = idx + lowbit(idx);
    }
}

区间查询 链接到标题

例如求 $[a, b]$ 之间的和。

int getsum(vector<int> &c, int idx) {
    int res = 0;
    while (idx > 0) {
        res += c[idx];
        idx = idx - lowbit(idx);
    }
    return res;
}

int getsum(vector<int> &c, int a, int b) {
    return getsum(c, b) - getsum(a - 1);
}