树状数组
树状数组是线段树的低配版，一旦掌握，写起来将会非常快（树状数组主要赢在快）。树状数组的具体原理可以参见 OI-wiki 中的相关论述。
定义和用处¶
树状数组常用于维护数组的区间和。此时原数组为 $a[1,2,\cdots,n]$，那么数组 $c[1,2,\cdots,n]$ 用于维护关于数组 $a$ 的“和”的信息。对于任意的 $c[x]$，它维护的是 $\sum _ {i=l(x)}^x a[i]$，其中 $l(x)=x-\operatorname{lowbit}(x)+1$。
注意这里的下标必须是 $1$ 开始一直到 $n$。$0$ 不能作为下标，是因为 $\operatorname{lowbit}$ 函数的特殊性。
树状数组的用处类似于线段树，可以在 $O(\log n)$ 的时间复杂度内完成下面任一操作：
- 单点修改。
- 区间查询。
单点修改¶
以维护区间和为例，一旦修改了 $a[x]$，需要这样修改 $c$ 数组：
- 初始令 $x^\prime=x$。
- 修改 $c[x^\prime]$。在此例中，$a[x]$ 如果增加了 $d$，那么 $c[x^\prime]$ 也是要增加 $d$。
- 令 $x^\prime\leftarrow x^\prime+\operatorname{lowbit(x^\prime)}$。一旦 $x^\prime >n$，循环终止。
$a[x]$ 发生变化，自 $c[x]$ 开始向右修改数组 $c$。
区间查询¶
同样以维护区间和为例。我们这边只提供求 $\sum _ {i=1} ^ r a[i]$ 的接法，如果要求 $\sum _ {i=l} ^ ra[i]$，可以简单地进行一个变换：$\sum _ {i=l}^ra[i]=\sum _ {i=1} ^ ra[i]-\sum _ {i=1} ^ {l - 1}a[i]$。
很容易写出这个求和的过程：
- 初始令 $x^\prime = x,s=0$。
- $s\leftarrow s+c[x]$。
- 更新 $x^\prime\leftarrow x^\prime-\operatorname{lowbit}(x^\prime)$。一旦 $x^\prime = 0$，循环终止。（注意这里的 $x^\prime$ 永远是非负数）。
$a[1]$ 到 $a[x]$ 区间求和，从 $c[x]$ 开始向左进行跳跃叠加。