问题

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

• 单点修改：将 $A[x]$ 加上 $k$；
• 区间查询：查询 $A[l]\cdots A[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;
}

暴力算法（$\times$）	树状数组（$\surd$）
单点修改	$O(1)$	$O(\log n)$
区间查询	$O(n)$	$O(\log n)$
$m$ 次操作	$O(mn)$	$O(m\log n)$

构造

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

rankdir=TB;
node [@s=box, @gray];
@neato;
#h1 = 0.6; #h2 = 1.2; #h3 = 1.8; #h4 = 2.4;
#w1 = height=0.3, width=0.5;
#w2 = height=0.3, width=1;
#w3 = height=0.3, width=2;
#w4 = height=0.3, width=4;
C8[@n="$C_8$", @(1.75,#h4), #w4];
aC8[@(3.25,#h4), style=invis];
C4[@n="$C_4$", @(.75,#h3), #w3];
aC4[@(1.25,#h3), style=invis];
C2[@n="$C_2$", @(.25,#h2), #w2]; C6[@n="$C_6$", @(2.25,#h2), #w2];
aC2[@(.25,#h2), style=invis]; aC6[@(2.25,#h2), style=invis];
C1[@n="$C_1$", @(0,#h1), #w1]; C3[@n="$C_3$", @(1,#h1), #w1]; C5[@n="$C_5$", @(2,#h1), #w1]; C7[@n="$C_7$", @(3,#h1), #w1];
A1[@n="$A_1$", @(0,0), #w1];
A2[@n="$A_2$", @(.5,0), #w1];
A3[@n="$A_3$", @(1,0), #w1];
A4[@n="$A_4$", @(1.5,0), #w1];
A5[@n="$A_5$", @(2,0), #w1];
A6[@n="$A_6$", @(2.5,0), #w1];
A7[@n="$A_7$", @(3,0), #w1];
A8[@n="$A_8$", @(3.5,0), #w1];
C1->A1; C3->A3; C5->A5; C7->A7;
aC2->C1,A2[tailport=se]; aC6->C5,A6[tailport=se];
aC4->C2,C3,A4[tailport=se];
aC8->C4,C6,C7,A8[tailport=se];

• $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$

我们不用立即知道每个 $C_i$ 代表的是哪一段的和。

初始时，将所有节点值设置成 0，就可以直接进行下文的 单点修改 和 区间查询。

父节点

如何求 $C_i$ 的父节点？

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

rankdir=TB;
node [@s=box, @gray];
@neato;
#h1 = 0.6; #h2 = 1.2; #h3 = 1.8; #h4 = 2.4;
#w1 = height=0.3, width=0.5;
#w2 = height=0.3, width=1;
#w3 = height=0.3, width=2;
#w4 = height=0.3, width=4;
C8[@n="$C_8$", @(1.75,#h4), #w4];
aC8[@(3.25,#h4), style=invis];
C4[@n="$C_4$", @(.75,#h3), #w3];
aC4[@(1.25,#h3), style=invis];
C2[@n="$C_2$", @(.25,#h2), #w2]; C6[@n="$C_6$", @(2.25,#h2), #w2];
aC2[@(.25,#h2), style=invis]; aC6[@(2.25,#h2), style=invis];
C1[@n="$C_1$", @(0,#h1), #w1]; C3[@n="$C_3$", @(1,#h1), #w1]; C5[@n="$C_5$", @(2,#h1), #w1]; C7[@n="$C_7$", @(3,#h1), #w1];
A1[@n="$A_1$", @(0,0), #w1];
A2[@n="$A_2$", @(.5,0), #w1];
A3[@n="$A_3$", @(1,0), #w1];
A4[@n="$A_4$", @(1.5,0), #w1];
A5[@n="$A_5$", @(2,0), #w1];
A6[@n="$A_6$", @(2.5,0), #w1];
A7[@n="$A_7$", @(3,0), #w1];
A8[@n="$A_8$", @(3.5,0), #w1];
C1->A1; C3->A3; C5->A5; C7->A7;
aC2->C1,A2[tailport=se]; aC6->C5,A6[tailport=se];
aC4->C2,C3,A4[tailport=se];
aC8->C4,C6,C7,A8[tailport=se];

C1 [@n="$C_{0001}$", #w1]
C2 [@n="$C_{0010}$", #w2]
C3 [@n="$C_{0011}$", #w1]
C4 [@n="$C_{0100}$", #w3]
C5 [@n="$C_{0101}$", #w1]
C6 [@n="$C_{0110}$", #w2]
C7 [@n="$C_{0111}$", #w1]
C8 [@n="$C_{1000}$", #w4]

• $C[0001]$ 的父节点为 $C[0010]$；
• $C[0100]$ 的父节点为 $C[1000]$；
• $C[0101]$ 的父节点为 $C[0110]$；
• $\cdots$

总结出规律：

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

左邻节点

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

rankdir=TB;
node [@s=box, @gray];
@neato;
#h1 = 0.6; #h2 = 1.2; #h3 = 1.8; #h4 = 2.4;
#w1 = height=0.3, width=0.5;
#w2 = height=0.3, width=1;
#w3 = height=0.3, width=2;
#w4 = height=0.3, width=4;
C8[@n="$C_8$", @(1.75,#h4), #w4];
aC8[@(3.25,#h4), style=invis];
C4[@n="$C_4$", @(.75,#h3), #w3];
aC4[@(1.25,#h3), style=invis];
C2[@n="$C_2$", @(.25,#h2), #w2]; C6[@n="$C_6$", @(2.25,#h2), #w2];
aC2[@(.25,#h2), style=invis]; aC6[@(2.25,#h2), style=invis];
C1[@n="$C_1$", @(0,#h1), #w1]; C3[@n="$C_3$", @(1,#h1), #w1]; C5[@n="$C_5$", @(2,#h1), #w1]; C7[@n="$C_7$", @(3,#h1), #w1];
A1[@n="$A_1$", @(0,0), #w1];
A2[@n="$A_2$", @(.5,0), #w1];
A3[@n="$A_3$", @(1,0), #w1];
A4[@n="$A_4$", @(1.5,0), #w1];
A5[@n="$A_5$", @(2,0), #w1];
A6[@n="$A_6$", @(2.5,0), #w1];
A7[@n="$A_7$", @(3,0), #w1];
A8[@n="$A_8$", @(3.5,0), #w1];
C1->A1; C3->A3; C5->A5; C7->A7;
aC2->C1,A2[tailport=se]; aC6->C5,A6[tailport=se];
aC4->C2,C3,A4[tailport=se];
aC8->C4,C6,C7,A8[tailport=se];

A1, A2, A3, A4, C4 [@blue]
A5, C5 [@green]

观察同一张图：

rankdir=TB;
node [@s=box, @gray];
@neato;
#h1 = 0.6; #h2 = 1.2; #h3 = 1.8; #h4 = 2.4;
#w1 = height=0.3, width=0.5;
#w2 = height=0.3, width=1;
#w3 = height=0.3, width=2;
#w4 = height=0.3, width=4;
C8[@n="$C_8$", @(1.75,#h4), #w4];
aC8[@(3.25,#h4), style=invis];
C4[@n="$C_4$", @(.75,#h3), #w3];
aC4[@(1.25,#h3), style=invis];
C2[@n="$C_2$", @(.25,#h2), #w2]; C6[@n="$C_6$", @(2.25,#h2), #w2];
aC2[@(.25,#h2), style=invis]; aC6[@(2.25,#h2), style=invis];
C1[@n="$C_1$", @(0,#h1), #w1]; C3[@n="$C_3$", @(1,#h1), #w1]; C5[@n="$C_5$", @(2,#h1), #w1]; C7[@n="$C_7$", @(3,#h1), #w1];
A1[@n="$A_1$", @(0,0), #w1];
A2[@n="$A_2$", @(.5,0), #w1];
A3[@n="$A_3$", @(1,0), #w1];
A4[@n="$A_4$", @(1.5,0), #w1];
A5[@n="$A_5$", @(2,0), #w1];
A6[@n="$A_6$", @(2.5,0), #w1];
A7[@n="$A_7$", @(3,0), #w1];
A8[@n="$A_8$", @(3.5,0), #w1];
C1->A1; C3->A3; C5->A5; C7->A7;
aC2->C1,A2[tailport=se]; aC6->C5,A6[tailport=se];
aC4->C2,C3,A4[tailport=se];
aC8->C4,C6,C7,A8[tailport=se];
C1 [@n="$C_{0001}$", #w1]
C2 [@n="$C_{0010}$", #w2]
C3 [@n="$C_{0011}$", #w1]
C4 [@n="$C_{0100}$", #w3]
C5 [@n="$C_{0101}$", #w1]
C6 [@n="$C_{0110}$", #w2]
C7 [@n="$C_{0111}$", #w1]
C8 [@n="$C_{1000}$", #w4]

• $C[0011]$ 的左邻节点为 $C[0010]$；
• $C[0101]$ 的左邻节点为 $C[0100]$；
• $C[0110]$ 的左邻节点为 $C[0100]$；
• $\cdots$

总结规律：

• $C_i$ 的左邻节点为 $C[i-$$\mathrm{lowbit}(i)]$。

单点修改

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

rankdir=TB;
node [@s=box, @gray];
@neato;
#h1 = 0.6; #h2 = 1.2; #h3 = 1.8; #h4 = 2.4;
#w1 = height=0.3, width=0.5;
#w2 = height=0.3, width=1;
#w3 = height=0.3, width=2;
#w4 = height=0.3, width=4;
C8[@n="$C_8$", @(1.75,#h4), #w4];
aC8[@(3.25,#h4), style=invis];
C4[@n="$C_4$", @(.75,#h3), #w3];
aC4[@(1.25,#h3), style=invis];
C2[@n="$C_2$", @(.25,#h2), #w2]; C6[@n="$C_6$", @(2.25,#h2), #w2];
aC2[@(.25,#h2), style=invis]; aC6[@(2.25,#h2), style=invis];
C1[@n="$C_1$", @(0,#h1), #w1]; C3[@n="$C_3$", @(1,#h1), #w1]; C5[@n="$C_5$", @(2,#h1), #w1]; C7[@n="$C_7$", @(3,#h1), #w1];
A1[@n="$A_1$", @(0,0), #w1];
A2[@n="$A_2$", @(.5,0), #w1];
A3[@n="$A_3$", @(1,0), #w1];
A4[@n="$A_4$", @(1.5,0), #w1];
A5[@n="$A_5$", @(2,0), #w1];
A6[@n="$A_6$", @(2.5,0), #w1];
A7[@n="$A_7$", @(3,0), #w1];
A8[@n="$A_8$", @(3.5,0), #w1];
C1->A1; C3->A3; C5->A5; C7->A7;
aC2->C1,A2[tailport=se]; aC6->C5,A6[tailport=se];
aC4->C2,C3,A4[tailport=se];
aC8->C4,C6,C7,A8[tailport=se];

C8, C4, C3, A3 [@purple]

• $C_3=$$A_3$；
• $C_4=$$A_1+$$A_2+$$A_3+$$A_4$；
• $C_8=$$A_1+$$A_2+$$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;
}

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

区间查询

参考 前缀和 思想：设 $\mathrm{sum}[x]=$$A[1]+$$A[2]+$$\cdots +$$A[x]$，则：

$$\sum _{i=l}^{r}A[i]=\mathrm{sum}[r]-\mathrm{sum}[l-1]$$

自此，问题转换为求任意的 $\mathrm{sum}[x]$。

以 $\mathrm{sum}[7]$ 为例：

rankdir=TB;
node [@s=box, @gray];
@neato;
#h1 = 0.6; #h2 = 1.2; #h3 = 1.8; #h4 = 2.4;
#w1 = height=0.3, width=0.5;
#w2 = height=0.3, width=1;
#w3 = height=0.3, width=2;
#w4 = height=0.3, width=4;
C8[@n="$C_8$", @(1.75,#h4), #w4];
aC8[@(3.25,#h4), style=invis];
C4[@n="$C_4$", @(.75,#h3), #w3];
aC4[@(1.25,#h3), style=invis];
C2[@n="$C_2$", @(.25,#h2), #w2]; C6[@n="$C_6$", @(2.25,#h2), #w2];
aC2[@(.25,#h2), style=invis]; aC6[@(2.25,#h2), style=invis];
C1[@n="$C_1$", @(0,#h1), #w1]; C3[@n="$C_3$", @(1,#h1), #w1]; C5[@n="$C_5$", @(2,#h1), #w1]; C7[@n="$C_7$", @(3,#h1), #w1];
A1[@n="$A_1$", @(0,0), #w1];
A2[@n="$A_2$", @(.5,0), #w1];
A3[@n="$A_3$", @(1,0), #w1];
A4[@n="$A_4$", @(1.5,0), #w1];
A5[@n="$A_5$", @(2,0), #w1];
A6[@n="$A_6$", @(2.5,0), #w1];
A7[@n="$A_7$", @(3,0), #w1];
A8[@n="$A_8$", @(3.5,0), #w1];
C1->A1; C3->A3; C5->A5; C7->A7;
aC2->C1,A2[tailport=se]; aC6->C5,A6[tailport=se];
aC4->C2,C3,A4[tailport=se];
aC8->C4,C6,C7,A8[tailport=se];

A1, A2, A3, A4, C4 [@blue]
A5, A6, C6 [@green]
A7, C7 [@yellow]

• $C_4=$$A_1+$$A_2+$$A_3+$$A_4$；
• $C_6=$$A_5+$$A_6$；
• $C_7=$$A_7$。

因而 $\mathrm{sum}[7]=$$C_4+$$C_6+$$C_7$。

查询 $\mathrm{sum}[x]$ 时，从 $C_x$ 开始依次遍历 左邻节点，累加其值。

时间复杂度为 $O(\log n)$。

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

// 查询 A[l] ... A[r] 的和
int get(int l, int 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$ 的差分数组 $f$ 上建立树状数组，其中 $f[i]=$$A[i]-$$A[i-$$1]$；
2. 将 $A[l]\cdots A[r]$ 都加上 $v$ 时，$f[l]$ 增加了 $v$，$f[r+$$1]$ 减少了 $v$。

由于 $A[i]=$$f[1]+$$f[2]+$$\cdots +$$f[i]$，所以可以通过区间查询得到 $A[i]$ 的值。

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

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

int main() {
    
    /* 输入部分省略 */
    
    for (int i = 1; i <= n; i ++) {
        // 在差分数组上建立树状数组
        add(i, a[i] - a[i - 1]);
    }
}