开始 NOI 前的总复习！近期可能会随机掉落一些类似的总结，时间关系可能不会写得很细，而且会省去一些严谨的证明
[5k+的“小小”总结].jpg
个人认为线段树和分块可以说是最常用、变化最多的数据结构了。这里先总结一下线段树吧。
列举的例题类型相似的将会被放在一起，同一类型的大致按难度排序。
Update：推荐阅读本文的修订版。因为已经发了洛谷日报，所以本文就不删了。
一、较复杂的 pushup 操作
线段树可以维护和、积、最值等满足结合律的区间运算。
这里总结几种常用且较复杂的信息
-
线段树维护矩阵
对于一些只有单点修改且维护的信息具有递推性的题目，由于运算具有结合律，可以将两区间合并写成矩阵乘法的形式，省去一些麻烦的讨论。
动态dp
在序列上时，可以直接将 dp 转移写成矩阵乘法的形式，方便维护。
在树上时，可以把树剖了，分别维护重链的信息 f 和轻链的信息 g。修改时，一条条链依次向上跳，每条链的信息用线段树维护，链首的父亲的 g 会被更新。当然也可以用全局平衡二叉树维护。
但写成矩乘的形式可能会带来巨大的常数，所以更好的做法是只维护矩阵中有用的值。（具体例子见 题解P3781 [SDOI2017]切树游戏
例题
- 题解 CF575A Fibonotci
- CF573D Bear and Cavalry
- CF1286D LCC
- P4719 【模板】"动态 DP"&动态树分治
- P6021 洪水
- 题解P3781 [SDOI2017]切树游戏
- P5281 [ZJOI2019]Minimax搜索（待填）
-
线段树维护直径
基于贪心的思想和直径的性质，当合并两个点集时，新直径的端点一定是被合并的两个点集直径四个端点中的某两个。但这个结论不适用存在负边权的情况。
另一种思路是把点拍扁到欧拉序上，两点间的距离即 dep_u+dep_v-2\min\limits_{i=u}^vdep_{i}。维护最大、最小深度 mx,mi，以及 lm=\max\{dep_u-2\min\limits_{i=l}^udep_i\},rm=\max\{dep_u-2\min\limits_{i=u}^rdep_i\} 和直径 s 。合并两个点集时，新点集的直径的两个端点要么全在左边（即 s_{lson}），要么全在右边（即 s_{rson}），要么跨越中点。具体转移见代码
void pushup(int ro)
{
t[ro].mx=max(t[ro<<1].mx,t[ro<<1|1].mx),t[ro].mi=min(t[ro<<1].mi,t[ro<<1|1].mi);
t[ro].lm=max(max(t[ro<<1].lm,t[ro<<1|1].lm),t[ro<<1|1].mx-2*t[ro<<1].mi);
t[ro].rm=max(max(t[ro<<1].rm,t[ro<<1|1].rm),t[ro<<1].mx-2*t[ro<<1|1].mi);
t[ro].s=max(max(t[ro<<1].s,t[ro<<1|1].s),max(t[ro<<1].mx+t[ro<<1|1].lm,t[ro<<1|1].mx+t[ro<<1].rm));
}
例题
- 题解 P2056 [ZJOI2007]捉迷藏
- P6845 [CEOI2019] Dynamic Diameter
-
线段树维护极小联通子树
例题
- P5327 [ZJOI2019]语言
- P3320 [SDOI2015]寻宝游戏
二、线段树维护线段/直线
即李超线段树。详见李超树学习笔记
三、线段树维护单调栈（前缀最值相关）
这部分讨论线段树如何维护前缀严格最大值相关信息。
以《楼房重建》为例，这题求的是前缀严格最大值的个数。
设 s 表示区间严格最大值的个数，mx 表示区间最大值，设 solve(ro,x) 表示 ro 所覆盖的区间中考虑前缀最大值 x 后的区间严格最大值个数
- 如果 x< mx_{ls} ，处于右区间的前缀最大值必定大于 mx_{ls}，所以也>x，则 x 不会对右区间造成影响。答案为 solve(ls,x)+s_{ro}-s_{ls}（注意，这里不是 s_{rs}）
- 如果 x\ge mx_{ls}，左区间所有的数都不可能成为前缀最大值，答案为 solve(rs,x)
由于每次只往一边递归，所以这个 solve 函数的复杂度是 O(\log n) 的。合并两个区间时，s_{ro}=s_{ls}+solve(rs,mx_{ls})，修改时会调用 O(\log n) 次 solve 函数，单次修改的复杂度为 O(\log^2n)。
但有时我们维护的信息不具有可减性（如取 \max,\min 等），为了让以上做法适应更一般的情况，我们更改 s 的定义为：只考虑 [l,r] 区间的影响时，[mid+1,r] 中的答案。那么 solve 函数中的第一种情况就可以改为 solve(ls,x)+s_{ro}，更新答案的操作改为 s_{ro}=solve(rs,mx_{ls})，同时查询操作要改为 solve(rt,0)
例题
-
P4198 楼房重建
-
P4425 [HNOI/AHOI2018]转盘
-
题解 CF671E Organizing a Race
经过一系列复杂的推导，问题转化为了维护 c_i=a_i-\min\limits_{j=1}^{i} b_j的最小值，支持 b 的区间加，查询 c_i\le k 的 i 的最大值。可以用维护前缀最值信息的线段树维护。具体地，线段树上每个节点维护 \min \{a_i\},\min \{b_i\}和仅考虑这个区间时右子树的答案 ans。对于修改操作，直接给 b 加，给 ans 减并打 tag 。对于 pushup 操作，用一个类似楼房重建的每次向一边递归的函数维护当前节点信息，代码长这样
ll pushup(int ro,int l,int r,ll p)
{
if(l==r)return t[ro].ami-p;
pushdown(ro);
return t[ro<<1].bmi<p?min(pushup(ro<<1,l,mid,p),t[ro].ans):min(t[ro<<1].ami-p,pushup(ro<<1|1,mid+1,r,p));
}
对于查询操作，一般情况下可以直接线段树上二分，但这里略有不同。考虑一个 query(ro,x) 操作，表示前缀最小值为 x 时 c_i\le k 的 i 的最大值
-
bmi_{ls}<x$ 时，$x$ 不影响右区间，那么 $ans_{ro}\le k$ 时向右子树递归，否则向左子树递归，时间复杂度为 $O(\log n)
-
bmi_{ls}\ge x$ 时，左子树完全被 $x$ 控制了。先向右子树递归，如果有合法的直接 return；否则在左子树中查$a_i-x\le k$ 的最大的 $i$ ，移项得 $a_i\le k+x$，这就是一个经典的线段树上二分了。因为最多进行 $O(\log n)$ 次线段树上二分，总复杂度为$O(\log^2n)
代码长这样
int query(int ro,int l,int r,ll &x)
{
if(l==r)
{
int tmp=t[ro].ami-x<=m?l:0;
x=min(x,t[ro].bmi);
return tmp;
}
pushdown(ro);
if(x>t[ro<<1].bmi)
{
if(t[ro].ans<=m)return query(ro<<1|1,mid+1,r,x=t[ro<<1].bmi);
int tmp=query(ro<<1,l,mid,x);
x=min(x,t[ro].bmi);
return tmp;
}
else
{
int tmp=(t[ro<<1].ami<=m+x?query2(ro<<1,l,mid,m+x):0);
return max(tmp,query(ro<<1|1,mid+1,r,x));
}
}
四、线段树维护历史值
-
历史最大值
（搬自我的题解 P4314 CPU监控）
先考虑如果只有加操作怎么做。假设每个点开了一个队列，存这个点被打过的所有标记，那么 pushdown 操作即为将父亲节点的队列中的元素全部放进儿子节点的队列，每放入一个值，则更新 x\leftarrow x'+tag,mx\leftarrow\max(mx,x)。但我们不可能真的存一个队列。设队列中加法标记的前缀和为 s[1\dots k]，则所有更新进行完后应有 x\leftarrow x'+s_k,mx\leftarrow\max\{x'+s_i\}=x'+\max\{s_i\}。那么我们只需要维护历史加的最大值即可。这个东西怎么维护呢？考虑合并两个队列（的前缀和）s_{son}[1\dots k_1],s_{fa}[1\dots k_2] 的过程
s_{son}[i]=\begin{cases}s_{son}'[i]\quad(i\le k_1)\\s'_{son}[k_1]+s_{fa}[i-k_1]\quad(k_1<i\le k_1+k_2)\end{cases}
则 \max\{s_{son}[i]\}=\max(\max \{s'_{son}[i]\},s_{son}'[k_1]+\max\{s_{fa}[i]\}) ，则我们需要维护 s_{son}[k_1] ，即目前的加法标记即可。总结一下，代码如下
void getsum(int ro,int sum,int hsum)//hsum:父节点上一次pushdown后的历史加法标记最大值
{
t[ro].hsum=max(t[ro].hsum,t[ro].sum+hsum);//历史加法标记最大值
t[ro].ans[1]=max(t[ro].ans[1],t[ro].ans[0]+hsum);//历史最大值
t[ro].ans[0]+=sum;//当前最大值
t[ro].sum+=sum; //当前加法标记
}
再加上赋值操作后，如果队列中有两种标记，不便于处理。可以发现，若存在一个赋值标记，则这个区间中的所有数会变成一样的，那么之后的加法标记都可以看成赋值标记。因此，此时的队列可以表示为一个加法标记队列紧跟着一个赋值标记队列。加法标记按上面说的处理。对于赋值标记 a[1\dots k]，最终产生的贡献即为 max\{a_i\}，再维护一个历史最大赋值标记即可。
例题
首先要注意到，这题是所有修改进行晚后再查询！
对于修改操作，可以看作在 l_1 时刻对 [l_2,r_2] 区间加 x ，在 r_1+1 时刻对 [l_2,r_2] 区间减 x，这样就把矩形的一维转变为了时间。询问变成了区间历史最大值。
如何查询规定时间区间的历史最大值呢？考虑对时间进行猫树分治，分别处理左、右区间内部的询问和跨越中点的询问。处理一个区间前保证 [1,l) 的修改已经进行，然后进行 [l,mid] 的修改。对于右区间，先打一个 tag 把历史最大值重置为当前最大值，边修改边处理询问，这样查询到的历史最大值就是 [mid,r] 时间的历史最大值了。然后撤回右区间的修改并再次重置历史最大值，在 [l,mid] 倒着撤回修改并查询历史最值。
实现时要注意的细节：如果有多个修改操作在同一时刻，必须按加的值从小到大处理，因为如果同时 +x,-y ，可能的历史最值应为 x-y 而非 x ；打重置标记前必须先下放标记。
-
历史版本和
问题：维护一个数列 A，要求支持区间加，区间查历史版本和。
记历史版本和序列为 B，并将“更新 B 序列”也看作一个操作，每次修改完都进行一次这个操作，进行这个操作的方法是给全局打上一个 upd 标记。记 sum 表示区间和，hsum 表示历史版本和，s[i] 表示前 i 个标记中加法操作的前缀和。仍然假设每个点开了一个队列，存这个点被打过的所有标记。队列中的元素对hsum 的贡献为
\sum[q[i]=upd](sum+s[i]\times len)=sum\sum[q[i]=upd]+len\sum[q[i]=upd]s[i]
则我们需要维护 \sum[q[i]=upd] 和 \sum[q[i]=upd]s[i]，即更新标记的个数和加法标记的历史版本和。合并两个队列时，更新标记的个数直接把两部分加起来即可
\begin{aligned}
&\sum[q_3[i]=upd]s_3[i]\\
=&\sum_{i=1}^{k_1}[q_1[i]=upd]s_1[i]+\sum_{i=1}^{k_2}[q_2[i]=upd](s_2[i]+s_1[k_1])\\
=&s_1[k_1]\sum[q_2[i]=upd]+\sum_{i=1}^{k_1}[q_1[i]=upd]s_1[i]+\sum_{i=1}^{k_2}[q_2[i]=upd]s_2[i]\\
\end{aligned}
再维护 s[k] ，即当前的加法标记即可。
例题：
五、线段树合并
当需要按对应位置合并一些数组，但这些数组并不满时，且合并操作较为简单（线段树能够支持）时可以采用线段树合并；同时也支持线段树所支持的区间修改、查询等操作。
一些问题中，线段树合并可以被长链剖分、dsu on tree 代替
下面介绍两种常见的应用
-
树上统计问题
例题
- P4556雨天的尾巴
- P3899 [湖南集训]谈笑风生
- 题解 P5327 [ZJOI2019]语言
-
优化 dp （整体dp）
例题
- P5298 [PKUWC2018]Minimax
- 题解 P6773 [NOI2020] 命运
- 题解 P4365 [九省联考2018]秘密袭击coat
六、线段树上二分
对于一些需要用二分套线段树上查询的问题，线段树本身就是一个分治的结构，所以可以直接在线段树的结构上进行二分。
例题
-
题解 P5537 【XR-3】系统设计
-
P4364 [九省联考2018]IIIDX
容易发现，i\to \lfloor\frac i k\rfloor 构成了一个树形结构。对于 d_i 互不相同的情况，把 d_i 从小到大排序后按子树大小分配后缀即可。
但当 d_i 相同时，可能会存在一种情况：可以将 u 子树内的一个较大值与 u 的兄弟交换使得答案更优。所以我们要改变贪心策略。设 cnt_i 表示 \ge i 的数的个数，cnt 是单调不降的。当我们选了一个数 x 放在当前子树 u 的根上，则 cnt[1,x] 全部要减小 siz_u（给子树预留位置），那么我们要找的实际上是 cnt_i\ge siz_u 的最大的 i 。区间减可以用线段树维护，查询直接在线段树上二分即可。
实现时要注意：如果一个点有父亲，那么查这个点的答案之前要把它父亲为子树预留的大小删去，且多个点父亲相同时只需要删一次。
七、线段树的结构分析
ZJOI经常有这样一类题目：模拟线段树上的一些操作，查询某种计数信息。这里将给出针对这些问题的几个结论
例题
-
题解 P5280 [ZJOI2019]线段树
-
P6630 [ZJOI2020] 传统艺能
对每个点算出其最终有 tag 的概率，相加即为答案。
分别计算出一次操作后每个节点作为以上 5 类点的概率，将操作对 f,g 的影响用矩阵表示出来，矩阵快速幂即可。
-
[1,n] 的广义线段树内 [l,r] 的区间定位数为 2\times (r-l+1)-|S|，其中 |S| 表示线段树上完全包含于 [l,r] 的区间数量。
证明：提取出所有包含于 [l,r] 区间的线段树上的区间，它们构成了一个完满二叉树森林。这个森林的叶子节点个数为 r-l+1，则森林的总点数为 2(r-l+1)-rt，其中 rt 表示根节点个数，也等价于区间定位数，移项得 rt=2(r-l+1)-|S|
例题
- P7143 [THUPC2021 初赛] 线段树 （也可以不用上面的结论，直接分治成两个子问题然后记搜）
-
广义线段树上 [l,r] 的区间定位可以这样表示：
记 L,R 分别表示 [l-1,l-1],[r+1,r+1] 对应的节点，记 U=lca(L,R)，则定位出来的区间为 L 到 U 的左儿子 的链上（下文称左链）所有节点的 不在链上的右儿子 和所有 R 到 U 的右儿子 的链上（下文称右链）所有节点的不在链上的左儿子
例题
设 [l,r] 的定位区间为 S
\sum_{v\in S}dis(u,v)=|S|dep_u+\sum_{v\in S}dep_v-2\sum_{v\in S}dep_{lca(u,v)}
分别维护 sizl_u,sizr_u,dl_u,dr_u 表示 u 的所有祖先的左/右儿子的兄弟的个数/深度和，|S| 和 \sum_{v\in S}dep_v 差分一下就可以得到。后半部分需要精细的讨论，以左链为例，记 u 和 L 的 lca 为 V
-
V$ 为 $U$ 或 $U$ 的祖先时，左链上所有的点和 $u$ 的 $lca$ 均 $V
- 否则，V 以上的点与 u 的 lca 为它的父亲，V 以下的点与 u 的 lca 为 V ；但当 u 恰好在为 V 的右儿子的子树里，u 和 V 的右儿子的 lca 就为 V 的右儿子
八、线段树优化建图
常见操作有三种：
-
从 x 向区间 [l,r] 的点连边
建一棵“正线段树“，其中父亲向儿子连边。找到 [l,r] 在“正线段树”上对应的节点，让 x 向这些点连边。
-
从区间 [l,r] 的点向 x 连边
建一棵“反线段树“，其中儿子向父亲连边。找到 [l,r] 在“正线段树”上对应的节点，让这些点向 x 连边。
-
从区间 [x,y] 的点向区间 [l,r] 的点连边
建一个虚点，让 [x,y] 在“反线段树”上对应的节点向虚点连边，虚点向“正线段树”上 [l,r] 对应的节点连边
对于有 n 个点，m 个连边操作的图，最终连出的总边数为 O(m\log n) 级别。
例题
- CF786B Legacy
- P5025 [SNOI2017]炸弹
- CF786E ALT
参考资料
-
从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法 （by 小粉兔）
-
关于线段树上的一些进阶操作（by command_block）
-
NOI 一轮复习 III：数据结构（by ix35）
就先总结这些吧，完结撒花！