树状数组

数组 $A$ 中共 $n$ 个元素，对其反复进行以下操作共 $m$ 次：

• 单点修改：将 $A[ x]$ 加上 $k$.

• 区间查询：查询 $A[l\cdots r]$ 的和.

int a[];

void set(int id, int v) { // 单点修改
    a[id] = v;
}

int ask(int l, int r) { // 区间查询
    int ans = 0;
    for(int i = l; i <= r; i ++)
        ans += a[i];
    return ans;
}

在原数组的上方构建树型结构，每个节点表示一段区间和：

$C_1=A_1$；

$C_2=A_1+A_2$；

$C_3=A_3$；

$C_4=A_1+A_2+A_3+A_4$；

$\cdots \ \cdots$

如何求 $C_i$ 的父节点？

将 $C$ 数组的下标转换成二进制数，观察该图.

• $C[$0001$]$ 的父节点为 $C[$0010$]$.

• $C[$0100$]$ 的父节点为 $C[$1000$]$.

• $C[$0101$]$ 的父节点为 $C[$0110$]$.

  $\cdots \ \cdots$

不难总结出规律：

• $C_i$ 的父节点为 $C[i+$ $lowbit(i)$ $]$.

$C_i$ 的「左邻节点」与 $C_i$ 的左端相邻.例如 $C_5$ 的左邻节点为 $C_4$.

观察同一张图：

• $C[$0011$]$ 的左邻节点为 $C[$0010$]$.

• $C[$0101$]$ 的左邻节点为 $C[$0100$]$.

• $C[$0110$]$ 的左邻节点为 $C[$0100$]$.

总结规律：

• $C_i$ 的左邻节点为 $C[i-lowbit(i)]$.

将 $A[x]$ 增加 $k$，$A[x]$ 的所有祖先都会跟着变动.以 $A_3$ 为例：

$C_3=\textcolor{red}{A_3}$；

$C_4=A_1+A_2+\textcolor{red}{A_3}+A_4$；

$C_8=A_1+A_2+\textcolor{red}{A_3}+A_4+A_5+A_6+A_7+A_8$.

因此，修改 $A[3]$ 的同时，$C_3,C_4,C_8$ 也需要加上 $k$.

对于给定的 $x$，从 $C_x$ 开始逐层访问 父节点，并给其值加上 $k$.时间复杂度为 $O(\log{n})$.

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

void add(int p, int k) { // 将 a[p] 增加 k
    for(; p <= n; p += lowbit(p)) c[p] += k;
}

采用 前缀和 思想.$sum[x]$ 表示 $A[1]+A[2]+\cdots+A[x]$，则：

自此，问题转换为求 $sum[x]$.以 $sum[7]$ 为例：

$C_4=A_1+A_2+A_3+A_4$；

$C_6=A_5+A_6$；

$C_7=A_7$；

因而 $sum[7]=C_4+C_6+C_7$.

查询 $sum[x]$ 时，从 $C_x$ 开始依次遍历 左邻节点.时间复杂度为 $O(\log{n})$.

int ask(int p) { // 查询 A[1...p] 的和
    int sum = 0;
    for(; p; p -= lowbit(p)) sum += c[p];
    return sum;
}

int get(int l, int r) { // 查询 A[l...r] 的和
    return ask(r) - ask(l - 1);
}

如果你已经学过 差分，区间修改就容易的多.

1. 在数组 $A$ 的「差分数组」上建立树状数组.

2. 将 $A[l\cdots r]$ 所有元素都加上 $v$ 时，$f[l]$ 增加了 $v$，$f[r+1]$ 减少了 $v$.

void seg_add(int l, int r, int v) { // 将 A[l...r] 加上 v
    add(l, v);
    add(r + 1, -v);
}

int main() {
    /* 输入部分省略 */
    for(int i = 1; i <= n; i ++) {
        add(i, a[i] - a[i - 1]);
    }
}