消灭线段树大常数暴政，世界属于树状数组。
挑战赛考虑出数据结构题吗？（
PART 0 基础知识
* 一点点的数学知识。
* 位运算知识：lowbit(x)\operatorname{lowbit}(x)lowbit(x) 表示 xxx 的二进制表示下最低位的一（与其后面的所有零构成的数）。
lowbit(x) = x & (-x)。
x←x−lowbit(x)x\gets x-\operatorname{lowbit}(x)x←x−lowbit(x) 等价于 x←xand (x−1)x\gets x\operatorname{and}\ (x-1)x←xand (x−1)。
PART 1 基本用法
PART 1.0 介绍
树状数组是一种支持单点修改和区间查询的高效数据结构。事实上，也可以通过一些进阶用法实现区间修改和单点查询，或者区间修改和区间查询，且渐进时空复杂度不会改变。
令当前树状数组的大小为 nnn，则单次修改或查询时间复杂度均为 Θ(logn)\Theta(\log n)Θ(logn)。空间复杂度则恒为 Θ(n)\Theta(n)Θ(n)。
一般的树状数组要求维护的信息满足结合律且存在逆运算。例如加法，模意义下的乘法（需保证逆元存在）等就满足上述条件，而类似于 max\maxmax，min\minmin 等不存在逆运算，就无法直接维护。（事实上这一类存在结合律而不存在逆运算的也可以用树状数组维护，但是时间复杂度会退化为 Θ(log2n)\Theta(\log^2 n)Θ(log2n)，劣于线段树的 Θ(logn)\Theta(\log n)Θ(logn)，所以不作讨论。）
发现树状数组使用的条件（结合律，逆运算）是使用线段树（结合律）的充分不必要条件，而二者的时空复杂度严格相等，看起来线段树还更全能一些，树状数组显得优势不大。但是树状数组的优势在于：
* 时间常数小。树状数组只需要用 while 循环迭代，而线段树需要进行复杂的递归过程。zkw 线段树消去了递归过程，但常数仍然较大。
* 空间常数小。树状数组只需要一倍空间，而线段树需要至少二倍空间，极端情况可能会达到树状数组的数倍。
* 编程复杂度低。树状数组只需要几次简单的迭代，代码长度只有十几行甚至更少；而线段树一般都需要数十上百行。
所以学习树状数组还是很有用的。
PART 1.1 引入
一个简单的问题：假如我想知道 a1..11a_{1..11}a1..11 的和，怎么算？
显然可以直接累加，需要将 111111 个数都加一遍。
那么假如我知道了 a1..8a_{1..8}a1..8 ，a9..10a_{9..10}a9..10 ，a11..11a_{11..11}a11..11 这三段分别的和，还可以怎么求？
显然直接把这三段的和加起来即可，只需要计算 333 个数的和。
这便是树状数组的核心思想：将求 [1,n][1,n][1,n] 的结果拆分成不超过 logn\log nlogn 个子问题，使得这些子问题的答案是已知的。 这也是运算需要满足结合律的原因。
令 cic_ici 为树状数组以下标 iii 结尾掌管的一个区间（区间大小在下面给出）的和。例如我们有 111111 个元素，树状数组 ccc 的结构是长这样的：
PART 1.2 区间查询
观察上图。发现 c8c_8c8 是 [1,8][1,8][1,8] 的和， c10c_{10}c10 是 [9,10][9,10][9,10] 的和，c11c_{11}c11 是 [11,11][11,11][11,11] 的和。因此 [1,11][1,11][1,11] 的和就是 c8+c10+c11c_8+c_{10}+c_{11}c8 +c10 +c11 。那么这个式子是我们肉眼发现的，有没有一般性的方法得到要把哪几个元素加起来呢？
首先，先考虑每一个索引掌管区间的长度如何确定。观察下表：
iii 区间长度 (i)2(i)_2(i)2 1 1 (0001) 2 2 (0010) 3 1 (0011) 4 4 (0100) 5 1 (0101) 6 2 (0110) 7 1 (0111) 8 8 (1000) 9 1 (1001) 10 2 (1010) 11 1 (1011)
发现 iii 掌管的区间长度为 lowbit(i)\operatorname{lowbit}(i)lowbit(i)（定义在 Part 0 给出）。因此得到结论：cxc_xcx 就是为 [x−lowbit(x)+1,x][x-\operatorname{lowbit}(x)+1,x][x−lowbit(x)+1,x] 的和。
知道了区间长度，接下来考虑查询。例如查找 [1,11][1,11][1,11] 的和：
* c11c_{11}c11 包含了 [11,11][11,11][11,11] 区间。加入答案，跳到左端点的前一个 ccc，也就是 c10c_{10}c10 。
* c10c_{10}c10 包含了 [9,10][9,10][9,10] 区间。加入答案，跳到左端点的前一个 ccc，也就是 c8c_{8}c8 。
* c8c_{8}c8 包含了 [1,8][1,8][1,8] 区间。加入答案，跳到左端点的前一个 ccc，也就是 c0c_{0}c0 。
* c0c_0c0 不存在，结束过程。
图：
有了上述思路，很容易用迭代实现查询 [1,k][1,k][1,k] 的和：
求 [x,y][x,y][x,y] 的和，使用前缀和的思想，结果显然为 query(y)-query(x-1)。
时间复杂度正确性：每一次对 kkk 的修改都会去除 kkk 二进制下的一个 1。kkk 的位数为 logk\log klogk，因此时间复杂度为 Θ(logk)\Theta(\log k)Θ(logk)。
PART 1.3 单点修改
设要更改 kkk 的值。为了保证效率，我们只需要更改 kkk 及其所有直接或间接祖先。由于 ckc_kck 包含于 ck+lowbit(k)c_{k+\operatorname{lowbit}(k)}ck+lowbit(k) （证明见后文），所以我们可以这样做：每一次修改后将索引自增其 lowbit\operatorname{lowbit}lowbit，直到索引超过范围。一个实现：
下说明 ck+lowbit(k)c_{k+\operatorname{lowbit}(k)}ck+lowbit(k) 包含 ckc_kck 。
令 x=log2lowbit(k)x=\log_2 \operatorname{lowbit}(k)x=log2 lowbit(k)，y=k−2xy=k-2^xy=k−2x，z=k+lowbit(k)z=k+\operatorname{lowbit}(k)z=k+lowbit(k)。
则 z=y+2x+1z=y+2^{x+1}z=y+2x+1，同时 kkk 管辖的左边界为 y+1y+1y+1。容易得知 lowbit(z)≥2x+1\operatorname{lowbit}(z)\geq 2^{x+1}lowbit(z)≥2x+1。取最小值，此时 zzz 管辖的左边界为 z−2x+1+1z-2^{x+1}+1z−2x+1+1，简单推一下后可得 zzz 管辖的左边界小于等于 kkk 管辖的左边界。
因为 zzz 管辖的左边界 ≤k\leq k≤k 管辖的左边界 ≤k<z\leq k < z≤k<z，所以 czc_zcz （即 ck+lowbit(k)c_{k+\operatorname{lowbit}(k)}ck+lowbit(k) ）包含 ckc_kck 。证毕。
PART 1.4 初始化
一个显然的方式是 nnn 次单点修改，时间复杂度 Θ(nlogn)\Theta(n \log n)Θ(nlogn)。
当然还能做得更好。因为父亲的下标总是严格大于自己的下标，而父亲的值就是其所有直接儿子的子树加上自己得到的。所以我们从左往右遍历，逐个修改自己和直接父亲，将其加上自己的子树和就行了，有点类似于线段树建树的思想。时间复杂度 Θ(n)\Theta(n)Θ(n)。注意判断越界。
例题：【模板】树状数组 1
谷 link
ACGO link
PART 2 维护一个差分数组
可以通过维护一个差分数组实现区间修改，单点查询。
咕咕咕
例题：【模板】树状数组 2
谷 link
ACGO link
PART 3 维护两个树状数组
可以通过维护两个树状数组实现区间修改，区间查询。
例题：【模板】线段树 1
咕咕咕
谷 link
