本文重在记录线段树的各类应用技巧和各种相关问题，不会讲解线段树的原理及实现（当然也可以把这个看成一个大纲一样的东西，尽量做到每个板块由浅入深）。
基础准备
线段树是一个主要用于维护序列（或是集合）信息的数据结构，主要原理是预处理 O(\log) 个子区间的信息，而这些子区间之间的关系呈一棵二叉树结构，通过组合这些预处理好的信息得到被查询区间的信息（通常要求所维护信息具有可合并性）。
各种线段树变种
记序列长为 n ，维护的信息合并时间为 O(\alpha)
-
朴素线段树（堆式存储）：最典型的用法是维护区间和，当然也能维护矩阵乘法，哈希这些可合并信息，空间 O(n) （通常开 4 倍空间），查询和区间修改都是 O(\alpha\log n) 。还有一个线段树二分的操作 O(\log n)。
-
动态开点线段树：将朴素线段树的堆式存储改为只将有用的节点建出来而不是排满每一层，这样就节约了空间（不用开 4 倍了），其他同朴素线段树。通常用于维护值域（如果能离线的话，朴素线段树和离散化搭配通常效果也是一样的）。相较于朴素线段树，更是支持 O(n) 合并两颗线段树（在某些情况下多次合并也是 O(n) 的）。
-
可持久化线段树：字面意思，就是可持久化后的朴素线段树，能维护多个版本，但一般要求两个相邻版本之间的变化是 O(1) 的，所以很难做到朴素线段树的区间修改（除非能标记永久化），其他同朴素线段树。
-
主席树：全称可持久化动态开点线段树，就是可持久化了动态开点线段树。
-
势能线段树：在某些操作正常来讲并不支持信息的可合并性，但具有 “进行次数有限” 的性质，这时可以巧妙地设计线段树维护。
-
单侧递归线段树（线段树维护单调栈，
兔队树）：这个非常神秘，个人认为是利用线段树地结构将序列排成 O(\log n) 个段，再在这些段组成的序列上做单调栈的工作，只不过获取一个段的某些偏序信息时通常要在该段内做 O(\log n) 的递归，所以查询是 O(\log n) 的，其他同朴素线段树。
下面是这些线段树的各种用法及 trick 。
朴素线段树
-
P3372 【模板】线段树 1 ，线段树最基础的应用。
-
P3373 【模板】线段树 2 ，设计信息合并和查询规则的基础题。
-
P1438 无聊的数列 ，线段树配合差分。
-
P4513 小白逛公园 ，理解线段树能维护可合并信息。
核心合并规则：struct node{ //节点信息 int ls,//这个节点的最大前缀和 rs,//这个节点的最大后缀和 ans,//这个节点的最大子段和 sum,//这个节点的总和 }; node merge(node l,node r){ node res; res.ls=max(l.ls,l.sum+r.ls); res.rs=max(r.rs,r.sum+l.rs); res.ans=max({l.ans,r.ans,l.rs+r.ls}); res.sum=l.sum+r.sum; } -
P3870 [TJOI2009] 开关 ，线段树二分基础。
-
P10071 [CCO 2023] Triangle Collection 线段树维护括号匹配个数。
动态开点线段树
要用上动态开点线段树的话需求一般就两个：
-
-
要维护超长序列，但操作数只有 O(n) 级别，最典型的就是维护值域（这时可以看作维护了一个数字集合）。
-
P13825 【模板】线段树 1.5 动态开点线段树板子。
-
P5490 【模板】扫描线 & 矩形面积并 对横轴用扫描线，纵轴的值域用动态开点线段树维护。
-
-
- 要使用线段树合并。
-
P4556 【模板】线段树合并 / [Vani 有约会] 雨天的尾巴
并非板子，经典线段树合并和树上差分结合。
可持久化线段树/主席树
-
P3919 【模板】可持久化线段树 1（可持久化数组） 值得注意的是，可持久化数组的实现意味着许多数据结构都能通过可持久化线段树可持久化，比如并查集。
可持久化线段树还能干的就是让离线的扫描线在线（不带修），这很好理解，扫描线是按照某种顺序遍历了一个维度上的所有点，同时用数据结构维护这个点所在的另一个维度上的所有信息，从头到尾只用了一根线的变化求出答案，能这样做是因为题目有遍历的维度和时间维度重合的性质。
而通常相邻的扫描线的变化是 O(1) 的，所以借助持久化的力量能将每一条线保存下来，而将这些线组织在一起的正是可持久化线段树。
常见特征是：元素具有两个属性，然后可以根据这两个属性将元素视为点刻画到平面上，并且点的个数合理，于是就能用可持久化线段树维护这个平面（其实本质上还是维护序列），也可以理解为对横轴上每个坐标都开了一个线段树。
这么讲有点迷，具体的例题：
这题其实有更简单的方法，这里的两个属性：编号和美妙度，但字段和不好搞，所以变成：编号 i 和美妙度前缀和 sum_i ，然后这题就变为选前 k 大的元素二元组。选前 k 大可以经典地用优先队列干，但是二元组的数量是 n^2 的，所以得用主席树维护：对每个编号维护它前面出现过的 sum_j 集合，而相邻编号集合相差不大，是 O(1) 的，所以以编号为版本建立主席树，然后剩下就能套 n^2 选前 k 大的经典做法了。
// 初始构建主席树的代码
#define mfy(i,j,x,f) t.rt[i]=t.add(t.rt[j],x,f,-M,M);
for(int i=1;i<=n;++i){
t.rt[i]=t.rt[i-1];
if(i-l>=0)
mfy(i,i,sum[i-l],1);
if(i-r-1>=0)
mfy(i,i,sum[i-r-1],-1);
if(i-l>=0)
q.push((seg){sum[i]-qy(i,1),i,1});
}
这题先分讨：
-
\operatorname{lca([l,r])}\in \operatorname{subtree}(p) ：答案就是 \operatorname{dis}(p,\operatorname{lca([l,r])}) 。
-
else case ：
- [l,r] 分布在 p 的各个分支：答案为 0 。
- [l,r] 只在 p 的一个分支：从 p 向祖先跳最小距离到祖先 A 使得 A 中存在 [l,r] 的任一点，答案就是这个距离。可以树剖，然后在每一条重链上二分。
从这里可以看出其实只要搞出 O(1)\sim O(\log) 查 [l,r] 是否在 p 子树或是整棵树除去 p 子树的部分就可以了。那么这个很容易想到 \operatorname{dfn} 序，这里同样以编号和 \operatorname{dfn} 序作为两个属性构建平面（编号同样作为版本号），问题就变成了问一个横向范围 [l,r] ，纵向范围 [l_1,r_1] 的矩形中是否有点，利用前缀和对线段树的设计是简单的。
// 编号区间 [l,r] 中是否存在点的 dfn 在 [l1,r1] 内。
// t.query(ver,l,r) 是版本 ver 在 dfn 范围 [l,r] 的版本前缀和
bool is_in(int l,int r,int l1,int r1){
if(r<l||r1<l1)return 0;
return t.query(t.rt[r],l1,r1)-t.query(t.rt[l-1],l1,r1);
}
势能线段树
这个比较灵活，需要结合具体要维护的运算具体设计线段树，但一般想出操作有效性的判定方法就没什么问题。
-
P4145 上帝造题的七分钟 2 / 花神游历各国 注意到开平方的次数经过 O(\log) 次就变成 1 了，所以有效操作总共也就 O(n\log) ，于是可以暴力给每个数直接去开平方，每个区间维护是否还有非 1 即可。
-
P9989 [Ynoi Easy Round 2023] TEST_69 这个也是，有效操作不超过 O(n\log) ，证明是容易的。而是否有效的判定则变为了这个区间内是否有数被 x 整除。可以维护区间 \operatorname{lcm} 。
-
CF438D The Child and Sequence 复杂度同理，记一下最大值和区间和就行。
单侧递归线段树
这个东西感觉就是，会了原理就基本会做题了，然而它的原理感觉十分难懂。。。
放一道最经典的题：P4198 楼房重建