Segment Tree

动机

询问

给你一个数组, 如何快速计算任何一段连续子数组的元素和?

对于一个子数组来说, 如果遍历子数组的每个数, 把它们加起来, 时间复杂度是$O(n)$, 太慢了.

下标从$left$到$right$的子数组元素和, 可以看成是下标从1到right的子数组元素和, 减去下标从1到left-1的子数组元素和. 例如数组$[3,1,4,5,9]$, 子数组$[4,1,5]$的元素和, 等于$[3,1,4,1,5]$的元素和, 减去$[3,1]$的元素和.

按照这个方法, 算出每个前缀$[1,i]$ (表示下标从$1$到$i$的连续子组)的元素和, 就可以$O(1)$地计算任意连续子数组的元素和了.

更新

但是, 如果还可以修改数组中的元素呢?

比如我把下标为1的元素修改了, 由于所有前缀都包含下标1, 那么就需要更新所有前缀的元素和, 更新操作就需要$O(n)$的时间, 这太慢了.

能不能把前缀$[1, i]$拆分成若干段连续子数组呢?

如果拆分得太细, 比如拆分成$[1,1],[2,2],[3,3],...$, 虽然更新是$O(1)$的, 但计算子数组元素和还是得遍历累加, 时间复杂度是$O(n)$, 太慢了.

平衡

上面的做法, 要么询问是$O(1)$更新是$O(n)$, 要么询问是$O(n)$更新时$O(1)$, 时间差距悬殊.

如何平衡询问和更新的时间复杂度?

关键在于如何拆分子数组(区间).

能否把任意前缀拆分成若干个关键区间, 使得更新操作也只会更新若干个关键区间?

这样回答询问时, 只需要遍历并累加若干个关键区间的元素和.

如何拆分?

启示: 如果把一个正整数$i$拆分成若干个不同的2的幂(从大到小), 那么只会拆分$O(logi)$个数. 前缀能否也这样拆分呢?

举个例子, $13=8 + 4 + 1$, 那么前缀$[1,13]$可以拆分成三个长度分别为$8,4,1$的关键区间: $[1,8], [9, 12], [13,13]$.

按照这个规则, 来看看从$[1,1]$到$[1,8]$是如何拆分的: $$ & [1,1] = [1,1] \ (1 = 1) \ & [1,2] = [1,2] \ (2 = 2) \ & [1,3] = [1,2] + [3,3] \ (3 = 2 + 1) \ & [1,4] = [1,4] \ (4 = 4) \ & [1,5] = [1,4] + [5,5] \ (5 = 4 + 1) \ & [1,6] = [1,4] + [5,6] \ (6 = 4 + 2) \ & [1,7] = [1,4] + [5,6] + [7,7] \ (7 = 4 + 2 + 1) \ & [1,8] = [1,8] \ (8 = 8) $$ 数一数, 按照这种拆分方式, 总共有多少个不同的关键区间? (提示: 把注意力放在区间的右端点上).

有$8$个: $[1,1], [1,2], [3,3], [1,4], [5,5],[5,6],[7,7],[1,8]$.

一般地:

如果$i$是$2$的幂, 那么$[1,i]$无需拆分.
如果$i$ 不是$2$的幂, 那么先拆分一个最小的$2$的幂, 记作$lowbit(i)$ (例如$6$拆分出$2$), 得到长为$lowbit(i)$的关键区间$[i - lowbit(i) + 1, i]$, 问题转换成的$[1, i - lowbit(i)]$ 如何拆分, 这是一个规模更小的子问题.

总共有$n$个不同的关键区间.

证明: 按顺序拆分前缀$[1,1], [1,2], [1,3], ..., [1,n]$, 每次只会恰好拆出一个新的关键区间$[i -lowbit(i) + 1, i]$ (注意$[1, i - lowbit(i)]$)之前拆分过了, 不会产生新的关键区间), 所以一共有$n$个不同的关键区间.

算法

由于关键区间的右端点互不相同, 我们可以把右端点为$i$的关键区间的元素和保存在$tree[i]$中.

按照如下方法计算前缀$[1,i]$的元素和:

初始化元素和$s = 0$.
每次循环, 把$tree[i]$加到$s$中, 对应关键区间$[i - lowbit(i) + 1, i]$的元素和.
然后更新$i$ 为$i - lowbit(i)$, 表示接下来要拆分$[1, i - lowbit(i)]$, 获取其中关键区间的元素和.
循环直到$i = 0$ 为止.
返回$s$.

由于正整数$i$的二进制长度是