树状数组

问题 #

数组 $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;
}
暴力算法($\textcolor{red}{×}$) 树状数组($\textcolor{green}{√}$)
单点修改 $\textcolor{green}{O(1)}$ $\textcolor{green}{O(\log{n})}$
区间查询 $\textcolor{red}{O(n)}$ $\textcolor{green}{O(\log{n})}$
$m$ 次操作 $\textcolor{red}{O(mn)}$ $\textcolor{green}{O(m\log{n})}$

构造 #

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

$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]$,则:

$A[l\cdots r]$ 的和 $=sum[r]-sum[l-1]$

自此,问题转换为求 $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);
}

模板 #

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

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

int ask(int p) {
    int sum = 0;
    for(; p; p -= lowbit(p)) sum += c[p];
    return sum;
}

int get(int l, int 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]);
    }
}