板子
1.【模板】线段树 1
2.【模板】线段树 2
线段树结构分析
1.[THUPC2021 初赛] 线段树
$[1,n]$ 上的广义线段树内 $[l,r]$ 的最小拆分大小为 $2(r-l+1)-|S|$，其中 $S$ 为包含于 $[l,r]$ 的线段树节点。
证明
将包含于 $[l,r]$ 的线段树节点取出，形成满二叉树森林，根节点的个数为最小拆分大小。
叶子节点的个数为 $r-l+1$，那么 $|S|=2(r-l+1)-根节点的个数$。
2.[ZJOI2017] 线段树
$[l,r]$ 的拆分可以看成 $[l-1,l-1],[r+1,r+1]$ 与二者 lca，的路径的左/右儿子。
不想写了。。。
3.[ZJOI2019] 线段树
对点分类。。。
4.[ZJOI2020] 传统艺能
扫描线
这是一种思想。狭义上更偏向于计算几何。
1.【模板】扫描线
code 这里也可以维护区间最小值及其个数。
2.[IOI1998] [USACO5.5] 矩形周长Picture
3.[SDOI2009] HH的项链
区间 $[l,r]$ 转化为点 $(l,r)$，发现只需求每个点被覆盖个数，扫描线+树状数组实现。
事实上单纯从左到右扫描，用线段树动态维护信息就是扫描线思想了。这题也可以这样理解。
可持久化线段树
1.【模板】可持久化线段树 2
对下标扫描线，构建可持久化权值线段树。
2.Rmq Problem / mex
权值线段树维护每个值最后出现的位置。离线扫描线或可持久化线段树均可。
3.[CQOI2015] 任务查询系统
对时间扫描线，用权值线段树维护优先级，由于强制在线，用可持久化线段树即可。
4.Destiny
类似绝对众数为排序后第 $\left \lceil \frac{n}{2} \right \rceil$ 个元素。
记 $d=\left \lceil \frac{r-l+1}{k} \right \rceil$，查询区间第 $d,2d,…$ 大，判断次数是否符合即可。
可持久化线段树维护，时间复杂度 $O(kn\log n)$。
线段树合并
需要考虑的是两个叶子节点的合并和如何只取一个节点。
树上问题
1.雨天的尾巴
2.[NOIP2016 提高组] 天天爱跑步
可以把玩家拆成向上和向下的两条链，两条链时间均递减/增，与深度联系一下就能转化为雨天的尾巴。
整体 DP
对于树上 DP 问题，可用线段树维护其中一维，加入子节点时用线段树合并转移，可以优化时间和空间。
1.[PKUWC2018] Minimax
所有叶子节点都有概率被取到，先离散化一下，计算出根节点取第 $i$ 小权值的概率即可计算答案。
记 $f[u][i]$ 为 $u$ 节点取 $i$ 号权值（即为第 $i$ 小）的概率。由于子节点数小于 $2$ ，可以分讨一下
- 若 $u$ 为叶子节点，直接更新。
- 若 $u$ 只有一个子节点，直接取子节点的值。
- 若 $u$ 有两个子节点。
可以前缀和后缀和优化 $O(n^2)$ 暴力计算。
考虑权值线段树维护第二维区间和（其实就是概率和）。需要合并两个子节点的值，考虑其中一个节点为空的情况，发现另一个节点的所有值都需要乘同一个值，写一个区间乘即可。具体实现时，一边合并，一边记录前缀后缀和。
2.[NOI2020] 命运
考虑树上 DP。在枚举 $u$ 点时，需要管的链肯定是下端点在子树中且未被满足的，此时应考虑 $u$ 到子节点的边的取值。
不难发现只需要考虑上端点在 $u$ 上方且深度最大的链，如果它被满足，则其他所有链都被满足（在 $u$ 上方这个限制不用特意注意）。
可以记 $f(u,i)$ 为下端点在 $u$ 的子树内且未被满足的链的上端点的最大深度为 $i$ 的方案数。每次加一个子节点转移
与前缀和有关，且开始有值的点很少，用线段树合并优化。具体实现时在 merge 中记录两棵线段树的前缀和可以减少查询的 $\log$。对于 $sum(u,i-1)$ 在有个节点为空时不需要管，因为空节点值为 $0$。当 $l=r$ 时，需要考虑，应该后更新该节点的前缀和。时间复杂度 $O(n\log n)$。
线段树分裂
1.【模板】线段树分裂
code 还可以平衡树合并。
树套树
李超线段树
支持插入线段，查询某位置交点最值。
1.【模板】李超线段树 / [HEOI2013] Segment
2.丝之割
为了方便，先将第一行反转一下，并将线的位置加 $1$。一些被包含的线是没用的将其去掉。剩下的按第一行的位置排序，第二行的位置是单减的。
考虑 DP，记 $f(i)$ 为处理到第 $i$ 个的最小花费。转移显然可以斜率优化。用李超线段树即可，时间复杂度 $O(n\log n)$（是单 $\log$ 因为是插入直线）。
3.Escape Through Leaf
暴力树上 DP 显然，用李超线段树合并维护。线段树合并的时间复杂度是 $O(n\log n)$ 的，第一篇题解有势能分析。
dsu on tree 可以做到 $O(n\log^2n)$。
4.Sum of Prefix Sums
有点类似直径，但是很复杂，不能 DP 或贪心。考虑点分治，合并路径时用李超线段树。时间复杂度 $O(n\log^2n)$。
线段树维护矩阵
序列问题
1.Bear and Cavalry
树上问题
1.【模板】”动态 DP”&动态树分治
如果没有修改，我们可以简单用 DP 求解。记 $dp(u,0/1)$ 为 $u$ 的子树，$u$ 选或不选的最大独立集，有
对于每个点选出一个特殊的子节点 $x$，记 $f_u=\sum_{v \ne x} \max(dp(v,0),dp(v,1))$，$g_u=\sum_{v \ne x}dp(v,0)+a[u]$。那么有
写成 $(\max,+)$ 广义矩阵乘法的形式就是
令 $x$ 为 $u$ 的重儿子，用线段树维护矩阵乘法，那么修改一个点，只会对 $O(\log n)$ 条重链造成影响。
2.[ZJOI2019] Minimax搜索
限制是取 $\max$ 的形式，考虑求出 $\max \le k$ 的方案数再差分。
考虑如何对单个 $k$ 快速求出答案。
记 $dp_u$ 为没有变化时 $u$ 点的值。那么 $1 \to dp_1$ 形成了一条 $dp$ 值都为 $dp_1$ 的链，只要链上任意节点的 $dp$ 值改变，答案一定改变。
对于叶子节点 $u$，若 $dep_{lca(u,dp_1)}$ 为奇数，那么若改变 $u$，则 $dp_u$ 变为 $dp_u + k$，偶数同理。
记 $f_u$ 为可以使 $dp_u \le dp_1$ 的方案数（叶子节点需要特判）$cnt_u$ 为 $u$ 子树中总方案数。答案为
$f$ 也是好计算的，就可以 $O(n)$ 求出特定 $k$ 的答案了。随着 $k$ 的变化，变化的 DP 值为某几个叶子节点，考虑动态 DP。记
这样转移式子优化为一个形式，动态 DP，时间复杂度 $O(n\log^2n)$。
线段树维护树上信息
维护直径
1.[CEOI2019] Dynamic Diameter
贪心
并集的直径端点一定在原四个端点中，线段树维护即可。时间复杂度 $O(n\log^2n)$，$O(1)$ 求 lca 可以优化到 $O(n\log n)$。
注意：贪心只有在边权非负的情况下才是对的。
dfs 序
一个节点无论访问还是回溯都记录下来，这样会得到一个长为 $2n-1$ 序列（ $rt$ 出现次数为$deg[rt]+1$ ，其他点出现的次数为 $deg[u]$ ），即为树的 dfs 序。
它有一个很好的性质：将原节点记为第一次出现的位置，则 $\min_{i=u}^{v} dep[i] = dep[lca(u,v)]$ ，考虑 dfs 过程不难理解。那么 $dis(u,v)=dep[u]+dep[v]-2\min_{i=u}^{v} dep[i]$。
用线段树维护直径 $s$，$\min_{u}dep[u]$，$\max_{u}dep[u]$，$\max_{u}\{dep[u]-2\min_{i=l}^{u}dep[i]\}$，$\max_{u}\{dep[u]-2\min_{i=u}^{r}dep[i]\}$。
注意：该方法仅适用于边权非负，这样才能保证区间中 dep 最小的点为 lca。
2.Tree Generator™
括号序列
构造一棵树的括号序列：dfs，向下就加‘（’，向上就加‘）’ 。长度为 $2*n-2$ ，因为每条边会被访问两次
性质一： 一段括号序列去掉对应的括号对应树的一条链（思考 dfs 过程）。
性质二： 一段括号序列去掉对应的括号所得序列的长度记为树上链的长度。
去掉对应括号的序列只有三种
))))))…
((((((…
)))…(((
考虑一般化，将‘（’视为 1， ‘）’视为 -1 ，则该链的长度为 $\max_{i=l-1}^{r}\{v(i+1,r)-v(l,i)\}$。直径即为最大的链长，类似最大子段和，用线段树维护。
维护最小连通子树
给定 $n$ 个关键点，动态维护 $n$ 个关键点所形成的最小连通子树大小。
将n个点按dfn序从小到大排序为 $0,2,…,n-1$ ，则子树大小为 $\frac{1}{2}\sum_{i=0}^{n-1}dis(i,(i+1)\%n)$。
1.[SDOI2015] 寻宝游戏
线段树
一般用于关键点
考虑如何合并，拆一下 $\%$
有点麻烦，考虑不维护 $dep[lca(l,r)]$
简单多了，最后减去即可。时间复杂度 $O(n\log^2n)$ ， $O(1)$ 求 lca 可做到 $O(n\log n)$。
set
非常简单的做法，直接维护最开始的式子，记 $ans$ 为最终答案。
每次加入 $u$ ，则 $ans+=dis(pre(u),u)+dis(u,nxt(u))-dis(pre(u),nxt(u))$。
每次减去 $u$ ，则 $ans+=dis(pre(u),,nxt(u))-dis(pre(u),u)-dis(u,nxt(u))$。
需要加入删除一个数，求前驱后继，用平衡树维护即可（可以用 set）。
2.[ZJOI2019] 语言
对于两元关系的统计，先固定一点 $u$，考虑如何求出 $(u,x)/(x,u)$ 的数量。
将所有经过 $u$ 的路径赋值为 1 ，统计 1 的个数，除以二即为答案。
树上的若干条链，经过同一个点，那么就形成了一个连通子树。
对于每个节点，我们都可以用线段树来维护最小连通子树。
差分，然后线段树合并即可，时间复杂度 $O(n\log^2n)$ ，同上可以优化为 $O(n\log n)$。
线段树优化建图
一般优化三种连边
$x \to [l,r]$
$[l,r] \to x$
$[l,r] \to [l’,r’]$
主要思想是建虚点代表一个区间。
1.Legacy
建一棵根向线段树，一棵叶向线段树。
我的 dij 板子怎么是错的？？？
2.「JOISC 2020 Day4」治疗计划
$O(m^2)$ 是简单的。考虑优化，套路地想数据结构优化。拆一下绝对值，如果 $i \to j$，那么
$t_j<t_i: r_i-t_i+1 \ge l_j-t_j$.
$t_j>t_i: r_i+t_i+1 \ge l_j+t_j$.
由于连向某个点的权值都相同，所以每个点在被枚举到时其 $dis$ 就已经确定。考虑快速找出邻点，这样均摊是对的。先按 $t$ 排序，然后线段树，时间复杂度 $O(n\log n)$。
单侧递归线段树
线段树分治
不如叫基于时间的分治。
1.二分图 /【模板】线段树分治
2.Painting Edges
一棵树，每条边有颜色（开始没有），当加入任意一种颜色的边时，图都为二分图，则此时合法。每次操作改变某条边的颜色，只有当改变后合法才会进行，判断每次操作是否会进行。
颜色很少，考虑对每个颜色开一个并查集维护。
我们并不能将操作离线下来，但每个时间只有一次操作，可以按时间先后线段树分治，先将操作挂在对应的叶子节点上，递归到该点时判断是否合法，并将对应区间进行覆盖（原颜色或更改的颜色）。
由于每次操作后图一定合法（不然不会操作），所以在叶子节点只需判断加入挂着的边后是否合法即可。
时间复杂度 $O(m\log q\log n+nk)$。
注意：不要手写栈，因为实际加入堆的元素个数为 $2(拆后的总边数)$ 而手写栈要开到 $2k(拆后的总边数)$ 空间会炸。