概述
-
线段树通过在原数组上建一棵二叉树，高效地处理各种结合性问题。
-
线段树的生命就在于 pushup 和 pushdown，更具体地，就在于结合性和差分性。
操作
- 线段树什么都支持！区间修改（加减乘，下取整除法和开方在数据合适的时候可以，吉老师版还可以 \(chkmin/max\)，...），区间查询（第\(k\)大/小，区间和/积，区间历史最值,...）。
复杂度分析
-
单次操作复杂度均摊 \(\log\) 级，吉老师版在区间加减和 \(chkmin/max\) 同时存在时为均摊 \(\log^2\) 级，否则是均摊 \(\log\) 级。
-
证明有两种，一种依赖于图论（树上二分），还有一种基于势能分析的（我不会）。下面的实现原理会讲到。
-
线段树的空间复杂度：静态开点（满二叉树存储）\(O(\approx2* n)\)，动态开点（\(m\) 为点的值域）\(O(n\log_2 m)\)。实际使用中一般开 \(4n\) 的大小。
扩展
-
吉老师线段树是一种线段树的大一统版本，可以以理论 \(\log^2\)，实际近均摊 \(\log\) 的复杂度为代价支持 \(chkmin/max\) 和区间历史最值。吉老师线段树相关的内容在后面。
-
线段树是一种可持久化数据结构，可持久化线段树也称为主席树。主席树相关的内容在后面。
-
线段树是一种可分裂合并数据结构。线段树分裂合并相关的内容在后面。
-
线段树是一种可以嵌套的数据结构，可以与线段树/平衡树/树状数组互相嵌套。树套树相关内容，请参看对应专题。
实现原理
-
我们定义一个“管辖范围”为线段树节点（下简称节点）对应的原数组的区间。每个节点都应当存储着它的子树的总信息，即，按题目需求结合起来的信息。
-
显然它的根的管辖范围为 \(1\sim n\) 。作为一棵二叉树，线段树上的非叶节点都将自己的管辖区间一分为二分给左右儿子，一般是 \(l\sim mid\) 和 \(mid+1\sim r\)，其中 \(mid=((l+r)>>1)\)。
-
静/动态开点线段树有着不一样的存点方式。静态开点线段树按照满二叉树方式存储，动态开点线段树每次插入或建树时访问到未建出的节点就将它新建出来并连边。
-
线段树的核心科技是 \(lazy\) 标记。\(lazy\) 标记的本质是延迟修改（也可以认为是合并修改），即：
-
如果还没有单独用到某一个节点的子树，就将它子树应该进行的修改存在它的 \(lazy\) 上，直到需要用到时再下传标记进行修改。
-
如果是整体用到这棵子树，可以利用它本身的信息加上可以直接算出的修改影响来作答。当然，某些操作，如下取整除法，开方等的影响无法算出，所以必须数据合适（例如这两者都可以证明单点的修改次数不超过 \(O(\log)\)，故可以使用线段树维护暴力）。
-
注意，下传标记进行修改并不是一修到底！ 事实上，我们每次都只修改下一层的节点，然后把 \(lazy\) 标记放在下一层的节点上。
-
线段树的操作大体上可以分为三种：修改，查询，维护（我们先不谈吉老师线段树）。
-
维护：以仅询问区间求和为例。在修改后，将当前节点的 \(sum\) 维护成 \(sum_{ls}+sum_{rs}\)，保证每个节点有正确的其管辖范围的结合性信息。
-
修改：以区间修改为例。我们需要传 \(6\) 个参数，分别为 \(now,l,r,L,R,val\)，代表当前在哪个节点，当前节点的管辖范围的左右端点，当前修改的区间的左右端点，对应区间应该加/减/乘/...的值。
-
从根节点开始修改，此时参数应该为 \((rt,1,n,L,R,val)\)。每到一个节点，首先判断它的管辖范围是否完全在修改范围内，如果是，则打标记，返回。如果不是，则判断左右子树管辖范围是否与之重合，如果是，则递归求解，然后维护当前节点信息。
-
询问：以询问区间求和为例。模仿修改，如果被包含直接回答，否则递归左右子树，回答两者之和。
-
复杂度证明
-
维护不计（归到修改和询问上作常数），单点修改/询问显然是 \(\log_2 m\)（跑满一条链）级别的，重点证明一下区间操作的复杂度，以区间询问为例。
-
我们把所有 return 的点定义为“到达点”，经过而没有 return 的点定义为“经过点”。
-
定理 \(1\)：任意 \(2\) 个“到达点”不为兄弟，即两者不拥有相同的直接父亲。
-
假设有至少 \(2\) 个到达点是兄弟，那么根据询问逻辑，应当在父亲处被合并作答，不成立。
-
故定理 \(1\) 成立。
-
-
定理 \(2\)：将所有到达点的管辖范围长度提取出来，得到的必然是一个广义单峰数列。
-
假设该数列除了单峰处外，还有其他转折然后递降的点，则必然形成谷。
-
对于一个谷点，我们找到它在原线段树上的对应节点，不断回溯直到它有至少一个兄弟（如果不回溯就有兄弟则违反定理 \(1\)）。
-
则此时它子树内有且仅有谷点代表的一段被询问，从而必然有至少一段没有被询问。
-
但我们知道谷点是在数列中间的。换句话说，整个询问区间可以做一定的拆分，使得在中间空出了一块。
-
这与区间询问的区间必须连续相矛盾，所以不成立。
-
所以定理 \(2\) 成立。
-
-
定理 \(3\)：任意一层不会有超过 \(2\) 个“到达点”。
-
假设有至少 \(3\) 个节点。由定理 \(1\)，三者互相不为兄弟。
-
由定理 \(2\)，三者又必须在广义单峰数列中连续，否则必然导致谷的出现。则三者连续，至少有两者为兄弟。
-
矛盾，所以定理 \(3\) 成立。
-
-
推论 \(1\)：因为线段树至多 \(\log_2 m\) 层，到达点总数不超过 \(2\log_2 m\)。
-
推论 \(2\)：提取出最左和最右的到达点，将根到他们的路径称为“主路径”，则其他到达点能且仅能经过 \(1\) 条边到达主路径。
-
能经过 \(1\) 条边：
-
假设某个到达点至少要经过 \(2\) 条边才能到达主路径。
-
则对其进行回溯，必然能找到一个节点不属于主路径同时又是该节点的祖先。
-
这个祖先的管辖范围一定有至少一段没有被包含，从而没有被询问。
-
但我们又知道这不是第一个/最后一个到达点（也即询问区间），则这与区间询问的区间必须连续矛盾，不成立。
-
-
只能经过一条边：这是个二叉树，树上路径唯一。
-
-
推论 \(3\)：单次询问访问到的点不超过 \(4\log_2 m\)。
- 两条主路径 \(2\log_2 m\)，中间的到达点数小于 \(2\log_2 m\)。
-
综上所述，我们证明了区间操作的复杂度也是严谨单次 \(O(\log m)\) 级别的；另一方面我们也认识到，线段树的常数确实比树状数组大上不少。
-
这里是应该有图的，但手搓图非常麻烦（这需要一个特别大的图），而且这个没有树状数组那么不显然，所以无限期推迟。
更多实现
-
线段树的标记永久化：一种对单点询问的优化。
-
更改询问方式。询问子树内单点时，每回溯一步，就将对应标记的操作赋到 \(ret\) 上。
-
于是永远都不需要下推标记，时间复杂度得到了优化。
-
主要运用于主席树。
-
-
多序列：考虑对序列 \(a,b\) 做区间修改和区间点积和查询。
-
维护 \(sum_a,sum_b,sum_{ab}\)，考虑对 \(a+v\)，于是 \(sum_{ab}=sum_{ab}+sum_b\times v\)。
-
可以推广到任意个序列，但显然需要维护 \(2^m+1\) 种信息，单次修改要改动的信息也很多，不想算了，总之不太实用。
-
应该也可以以同样的思路推广到其他简单操作。目前还没怎么写过，之后再说吧。
-
对于非经典操作，目前只知道 \(\min(a,b)\) 这类好像是李超树。
-
-
指针式：没学...那就是邪教（蚌）。另外啥是编译级？
区间判重
-
代表题目：\(\text{P3792 由乃与大母神原型和偶像崇拜}\)，\(\text{P5278 算术天才9与等差数列}\)，及稍有推广的 \(\text{P6617 查找 Search}\)。
-
题意：求区间 \([l,r]\) 内是否存在一对 \(match\)，这里的 \(match\) 可以是相同数，也可以是别的什么乱七八糟的定义。带单点修改。
-
考虑使用线段树维护数组 \(with\)，\(with_i\) 表示 \(<i\) 且能与 \(i\) 匹配的最大位置，于是问题变成 \([\max_{i=l}^r with_i\geqslant l]\)。
-
注意到这样修改量可能过大，譬如考虑令后 \(\dfrac{n}{2}\) 完全相同，开始时它们都没有匹配，然后依次将 \(1\sim \dfrac{n}{2}\) 修改成和它们匹配的，每次都有 \(O(n)\) 的修改量。这里的连续性显然是特例，不起作用。
-
故改定义，若有多个 \(with_i=j\)，则令最小的 \(i\) 的 \(with=j\)，其他的失配。可以证明，这不影响上面的问题转化，因为当且仅当最小的 \(i\) 被包含，对应 \(j\) 才可能被包含。
-
考虑怎么进行单点修改。在匹配对象可以 \(O(1)\) 计算出来的时候，我们通常使用 set 维护每个数字的出现位置，然后修改。这里以 \(match\) 的对象为相同数字为例，将修改拆成删除和插入：
-
删除：令后继与前驱匹配（注意这种匹配是单向的）。
-
插入：令后继与当前匹配，当前与前驱匹配。
-
-
推广到更为一般的情况，如查找那道题，就可能要考虑当前、前驱、后继、匹配的前驱、匹配的后继，较为复杂，主要有两种较为方便的实现方式：
-
格式化分类讨论，即将所有情况都用 if else 列出来，不进行无用情况清除和类同情况合并。优点是清晰，缺点是码量较大。
-
暴力重构对应区间。优点是好写，缺点是可能常数很大甚至复杂度更高。
-
-
可以和 set 结合维护更恶心的东西，事实上这时候线段树更多地只是个背景板，或者说区间求值已经不再是难度所在，例如 \(\text{P5069 [Ynoi2015] 纵使日薄西山}\)。
扩展：吉老师线段树
扩展：主席树
扩展：线段树分裂合并
扩展：线段树（及主席树）相关的树套树
- 请参看“树套树”。