树状数组

问题

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

单点修改：将 $A [x]$ 加上 $k$ ；
区间查询：查询 $A [l] \dots A [r]$ 的和。

cpp

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$ ）	树状数组（ $\sqrt$ ）
单点修改	$O (1)$	$O (\log n)$
区间查询	$O (n)$	$O (\log n)$
$m$ 次操作	$O (m n)$	$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}$ ；
$\dots$

我们不用立即知道每个 $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]$ ；
$\dots$

总结出规律：

$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]$ ；
$\dots$

总结规律：

$C_{i}$ 的左邻节点为 $C [i - 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)$ 。

cpp

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;
}

区间查询

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

\sum_{i = l}^{r} A [i] = sum [r] - sum [l - 1]

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

以 $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}$ 。

因而 $sum [7] = C_{4} + C_{6} + C_{7}$ 。

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

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

cpp

// 查询 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);
}

模板

cpp

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);
}

拓展

一般的树状数组只能实现「单点修改、区间查询」。

通过差分技巧，树状数组也可以实现「区间修改、单点查询」。

在数组 $A$ 的差分数组 $f$ 上建立树状数组，其中 $f [i] = A [i] - A [i - 1]$ ；
将 $A [l] \dots A [r]$ 都加上 $v$ 时， $f [l]$ 增加了 $v$ ， $f [r + 1]$ 减少了 $v$ 。

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

cpp

// 将 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]);
    }
}

同余

组合数学

数值分析

多项式

圆锥曲线

问题

构造

父节点

左邻节点

单点修改

区间查询

模板

拓展

树状数组

问题 ​

构造 ​

父节点 ​

左邻节点 ​

单点修改 ​

区间查询 ​

模板 ​

拓展 ​

问题

构造

父节点

左邻节点

单点修改

区间查询

模板

拓展