SegmentTree
SegmentTree
SegmentTree（线段树）
引导
10000个正整数，编号从1到10000，用A[1],A[2],A[10000]表示。
修改：1.将第L个数增加C （1 <= L <= 10000）
统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.
-
不修改，直接统计：
方法一：对于统计L,R ，需要求下标从L到R的所有数的和，从L到R的所有下标记做[L..R],问题就是对A[L..R]进行求和。
这样求和，对于每个询问，需要将(R-L+1)个数相加。方法二：更快的方法是求前缀和,令 S[0]=0, S[k]=A[1..k] ，那么，A[L..R]的和就等于S[R]-S[L-1]，
这样，对于每个询问，就只需要做一次减法，大大提高效率。 -
先修改，后统计：
用方法二的话，假如A[L]+=C之后，S[L],S[L+1],...,S[R]都需要增加C,全部都要修改。
-
对比：
| 方法一 | 方法二 | |
|---|---|---|
| A[L]+=C | 修改1个元素 （快） | 修改R-L+1个元素 |
| 求和A[L..R] | 计算R-L+1个元素之和 | 计算两个元素之差 （快） |
找一种，修改和求和都比较快的方式，即线段树。
概念
一种二叉树形数据结构，用以存储区间或线段，允许快速查询结构内包含某一点的所有区间和元素更新操作，也可以进行区间最大值、最小值、区间异或值的查询...
- 时间复杂度 $O(logN)$
- 空间复杂度 $O(N)$
N 表示区间数量
结构
将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。
这种数据结构可以方便的进行大部分的区间操作。
图示
单位区间：被端点切分的区间称为单位区间，每个端点所在位置也单独成为单位区间，比如：$(-\infty, x_1),[x_1,x_1],(x_1,x_2),[x_2,x_2],\dots,(x_{m-1},x_m),[x_m,x_m],(x_m,+\infty)$
线段树的结构为一个完全二叉树，每个节点都代表一个坐标区间，节点N所代表的区间记为Int(N)，则其需符合以下条件：
其每一个叶节点，从左到右代表每个单位区间。
其内部节点代表的区间是其两个儿子代表的区间之联集。
每个节点（包含叶子）中有一个存储线段的数据结构。若一个线段S的坐标区间包含Int(N)但不包含Int(parent(N))，则节点N中会存储线段S。
示例
有个大小为 5 的数组 a = {10, 11, 12, 13, 14}，要将其转化为线段树，
有以下做法：设线段树的根节点编号为 1，用数组 d 来保存我们的线段树，$d_i$ 用来保存线段树上编号为 i 的节点的值（这个节点所表示的区间总和），
如图所示（存储结构）：
注解：
紫色方框是数组$a$ , 红色方框是数组 $d$,
括号中黄色数字表示当前节点表示的区间，$d_1$ 表示的区间是$[1,5]$,
$d_1$ 所保存的值是 $d_1 = 60 = a1+...+a5$
发现基本规律
-
$d_i$ 的左孩子是 $d_{2i}$ , 右孩子是 $d_{2i+1}$；
-
如果用 $d_i$ 表示区间 $[s,t]$ 的值, 那么其左孩子表示区间 $[s, \frac{s+t}{2}]$, 右孩子表示区间$[\frac{s+t}{2}+1, t]$
-
如果$d_i$表示的区间大小等于$1$, 那么其区间 $[s,t]$ 中肯定有 $s=t$, 且 $d_i = a_s = a_t$ , 即叶节点，这也就是线段树的递归边界。
操作
建树
给定区间[L,R]，只要L < R ，线段树就会把它继续分裂成两个区间。
首先计算 M = (L+R)/2，左子区间为[L,M]，右子区间为[M+1,R]，然后如果子区间不满足条件就递归分解。
每两个叶子节点构成一个中间节点，直至根节点。
子节点的数据用于构建母节点中存储的值，每个中间节点代表它的左右两个子节点对应的区间融合过后的大区间的值。
这个融合的值，依据处理的问题不同而不同（min/sum/max/...）。
void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) { // 规律3
d[p] = a[s];
return;
}
int m = (s + t) / 2;
build(s, m, p * 2), build(m + 1, t, p * 2 + 1); // 规律2
// 递归对左右区间建树
d[p] = d[p * 2] + d[(p * 2) + 1]; // 规律1
}
展开子区间
给定区间[2,12]分解成上述区间进行计算
自下而上-利于理解
区间$[2,12]$的计算结果为： $[2]+[3,4]+[5,7]+[8,10]+[11,12]$
自上而下-利于计算
区间$[2,12]$的计算结果为： $[2]+[3,4]+[5,7]+[8,10]+[11,12]$
区间查询/统计
假设这13个数为1,2,3,4,1,2,3,4,1,2,3,4,1. 在区间之后标上该区间的数字之和：
区间$[2,12]$的计算结果为： $[2]+[3,4]+[5,7]+[8,10]+[11,12]$ = $2+7+6+7+7$ = 29
区间查询大体上可以分为3种情况讨论：
- 当前结点所代表的区间完全位于给定需要被查询的区间之外，则不应考虑当前结点
- 当前结点所代表的区间完全位于给定需要被查询的区间之内，则可以直接查看当前结点的父结点
- 当前结点所代表的区间部分位于需要被查询的区间之内，部分位于其外，则我们先考虑位于区间外的部分，后考虑区间内的（总有可能找到完全位于区间内的结点，因为叶子结点的区间长度为1，因此我们总能组合出合适的区间）
举例：查询区间$[l,r]$的和，如$[3,5]$区间，可拆分为$[3,4]$和$[5,5]$两个区间进行合并。
int getsum(int l, int r, int s, int t, int p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
if (l <= s && t <= r)
return d[p]; // 当前区间为询问区间的子集时直接返回当前区间的和
int m = (s + t) / 2, sum = 0;
if (l <= m) sum += getsum(l, r, s, m, p * 2);
// 如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
// 如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子
return sum;
}
单点修改
当输入数组中位于 i 位置的元素被修改时，需要从这个元素对应的叶子节点开始，沿二叉树路径向上更新至根节点。
把A[6]+=7，需要被修改的区间为：$[6],[5,6],[5,7],[1,7],[1,13]$，只需要修改五个元素，$logN$ 个节点。
区间修改
对指定区间内的每个元素进行相同的修改，除了遍历每个元素进行修改，复杂度是$O(NlogN)$，还可以通过懒惰标记（优化）完成，复杂度是$O(logN)$。
例：把区间 [1,7]每个元素+2，可以直接在 [1,7] 区间节点上，既权值 +$(7-1+1)*2$，并打上懒惰标记$2$，用于查询时下推标记。
参考：