线段树相关技巧的小小总结

开始 NOI 前的总复习！近期可能会随机掉落一些类似的总结，时间关系可能不会写得很细，而且会省去一些严谨的证明

~~[5k+的“小小”总结].jpg~~

个人认为线段树和分块可以说是最常用、变化最多的数据结构了。这里先总结一下线段树吧。

列举的例题类型相似的将会被放在一起，同一类型的大致按难度排序。

Update：推荐阅读本文的修订版。因为已经发了洛谷日报，所以本文就不删了。

一、较复杂的 pushup 操作

线段树可以维护和、积、最值等满足结合律的区间运算。

这里总结几种常用且较复杂的信息

线段树维护矩阵

对于一些只有单点修改且维护的信息具有递推性的题目，由于运算具有结合律，可以将两区间合并写成矩阵乘法的形式，省去一些麻烦的讨论。

动态dp

在序列上时，可以直接将 dp 转移写成矩阵乘法的形式，方便维护。

在树上时，可以把树剖了，分别维护重链的信息 $f$ 和轻链的信息 $g$ 。修改时，一条条链依次向上跳，每条链的信息用线段树维护，链首的父亲的 $g$ 会被更新。当然也可以用全局平衡二叉树维护。

但写成矩乘的形式可能会带来巨大的常数，所以更好的做法是只维护矩阵中有用的值。（具体例子见题解P3781 [SDOI2017]切树游戏

例题
线段树维护直径

基于贪心的思想和直径的性质，当合并两个点集时，新直径的端点一定是被合并的两个点集直径四个端点中的某两个。但这个结论不适用存在负边权的情况。

另一种思路是把点拍扁到欧拉序上，两点间的距离即 $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}$ ），要么跨越中点。具体转移见代码
CPP
```
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 操作，用一个类似楼房重建的每次向一边递归的函数维护当前节点信息，代码长这样
CPP
```
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)$
代码长这样
CPP
```
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]$ ，即目前的加法标记即可。总结一下，代码如下
CPP
```
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\}$ ，再维护一个历史最大赋值标记即可。

例题
- P4314 CPU监控
- P6349 [PA2011]Kangaroos （这个其实是 KDT，但维护 tag 的方法是相同的）
- P6109 [Ynoi2009] rprmq
  
  首先要注意到，这题是所有修改进行晚后再查询！
  
  对于修改操作，可以看作在 $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]$ ，即当前的加法标记即可。

例题：
- CF997E Good Subsegments

五、线段树合并

当需要按对应位置合并一些数组，但这些数组并不满时，且合并操作较为简单（线段树能够支持）时可以采用线段树合并；同时也支持线段树所支持的区间修改、查询等操作。

一些问题中，线段树合并可以被长链剖分、dsu on tree 代替

下面介绍两种常见的应用

树上统计问题

例题
优化 dp （整体dp）

例题

六、线段树上二分

对于一些需要用二分套线段树上查询的问题，线段树本身就是一个分治的结构，所以可以直接在线段树的结构上进行二分。

例题

题解 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~~经常有这样一类题目：模拟线段树上的一些操作，查询某种计数信息。这里将给出针对这些问题的几个结论

一些定义：
- 区间定位数： $[l,r]$ 区间最少拆成线段树上的多少个区间
- 广义线段树：分治点 $mid$ 为 $[l,r)$ 中的任意一个整数
modify 操作对 lazytag 的影响

设操作区间为 $[ql,qr]$ （图来自小粉兔的题解，侵删歉）
1. 若 $[l,r]\cap [ql,qr]=[l,r]$ 且它的父亲不满足上述性质（即下图中的浅蓝色部分），那么这个区间在这轮操作中一定会被覆盖到，即操作后它们必然有懒标记 。
2. 若 $[l,r]\cap [ql,qr]\neq \emptyset$ 且不满足性质①（即下图中的紫色部分），那么这个区间的 lazytag 一定会被下传， 即操作后它们必然无懒标记。
3. 若 $[l,r]\cap [ql,qr]=\emptyset$ 但它的父亲区间与 $[ql,qr]$ 有交集（即下图中的黄色部分），那么这个区间在这轮操作中只能接受祖先的 lazytag， 操作后它们有无懒标记取决于操作前这个节点到根的链上有无懒标记。
4. 若 $[l,r]\cap [ql,qr]=\emptyset$ 但它的父亲区间与 $[ql,qr]$ 交集为空（即下图中的橙色部分），那么这轮操作与这个区间无关
5. 若 $[l,r]\cap [ql,qr]=[l,r]$ 且它的祖先满足上述性质（即下图中的深蓝色部分），那么这个区间在这轮操作中一定不会被覆盖到。
总结一下，设 $f_i$ 表示 $i$ 是否有标记， $g_i$ 表示 $i$ 到根的路径上（包括 $i$ ）是否存在一个有标记的点
1. 浅蓝色部分： $f_i=g_i=1$
2. 紫色部分： $f_i=g_i=0$
3. 黄色部分： $f_i=g_i=g_i'$
4. 橙色部分： $f_i=f_i',g_i=g_i'$
5. 深蓝色部分： $f_i=f_i',g_i=1$

例题

题解 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$ 的右儿子的链上（下文称右链）所有节点的不在链上的左儿子 **

例题
- P5210 [ZJOI2017]线段树
  
  设 $[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)

级别。

例题

参考资料

就先总结这些吧，完结撒花！

线段树相关技巧的小小总结

文章操作

一、较复杂的 pushup 操作

线段树维护矩阵

动态dp

例题

线段树维护直径

例题

线段树维护极小联通子树

例题

二、线段树维护线段/直线

三、线段树维护单调栈（前缀最值相关）

例题

四、线段树维护历史值

历史最大值

例题

历史版本和

例题：

五、线段树合并

树上统计问题

例题

优化 dp （整体dp）

例题

六、线段树上二分

例题

七、线段树的结构分析

例题

例题

例题

八、线段树优化建图

例题

参考资料

相关推荐

评论

线段树相关技巧的小小总结