admin 的博客
关于线段树上的一些进阶操作
admin LV 10 SU @ 2026-7-10 10:47:22

关于线段树上的一些进阶操作更新于 2026/7/2 10:45:52 作者

command_block

前言

本文包含的内容有：

李超树
历史标记
$\text{Seg-beats}$
$\text{Kinetic Tournament tree}$ （未施工）

参考资料：

国家集训队2016论文集：吉如一《区间最值操作与历史最值问题》
国家集训队2020论文集：李白天《浅谈函数最值的动态维护》

云剪贴板：代码合集

杂项

$\bf\color{blue}\Delta$ 标记拼接

只是 pushup 的技巧，对于所有基于合并的数据结构都适用。

也可以理解为动态DP。

$\bf\color{blue}\Delta$ 点积

维护两个序列 $A,B$ ，支持区间加，查询 $A[i]*B[i]$ 的区间和。

设 $s_a,s_b,s_o$ 分别为 $A,B,(A·B)$ 的区间和。

则给 $A$ 整体加 $c$ 后, $s_o\leftarrow s_b*c$ 。

可以扩展到其他的操作，就不再赘述。

线段树合并

其实就是空间换时间。

考虑总点数一直在减小，而初始时只有 $O(n\log n)$ 个即可证明复杂度。

将二度点压缩后可以做到 $O(n)$ 空间，但一般不实用。

李超线段树

P4097 [HEOI2013]Segment

题意 : 要求维护一种数据结构，支持插入线段，查询某个 $x$ 坐标处所有线段取值的 $\max$ 。

考虑使用线段树维护。我们称某个区间的“优势线段”为在 $mid$ 处取值最大的线段。

当某个区间插入一条新线段的时候，应该与原有的线段比较 $mid$ 处的取值，如果更优则该点新线段占领。

然而,这个区间内仍然有一部分位置,使得旧线段更优。

由于两条一次函数最多只有一个交点,我们能够发现,旧线段更优的部分必然完全在 $mid$ 的左边或者右边。

那么我们把被击败的线段继续下放即可。

下放的复杂度是 $O(\log n)$ 的，而一条线段会被拆分成对 $O(\log n)$ 个点的直接操作，所以李超树的复杂度是 $O(log^2n)$ 的。实际上常数很小。

如果维护的不是线段集，而是直线集，复杂度是严格 $O(\log n)$ 的。

P4069 [SDOI2016]游戏

首先在 LCA 处把路径拆一下，变成一条向上的和一条向下的。

显然，题目中加数的形式可以转化成有关深度的一次函数。

我们把树剖一下，每条重链采用李超树维护即可。

虽然这里的 “ $x$ 坐标” 不是连续的，但仍然是单调的，可以维护。不必动态开点。

对于区间 $\min$ ，先维护子树 $\min$ 。注意李超树并不是 Leafy 的，更新信息要算上自身。

除此之外还有各个不在子区间内但能贡献的一次函数的 $\min$ ，这类似于标记永久化。由于单调性，只需要取区间内的左右端点即可。

千万不要把维护线段的李超树当做凸包来思考!

虽然复杂度是 $O(n\log^3 n)$ ，但是李超树和树剖的常数都很小，效率还行。

调了很久，友情提供样例 : Link

评测记录

P4655 [CEOI2017]Building Bridges

我们把拆除与不拆除翻转过来，先全部都拆除，再减去不拆除的贡献。

可以得到这样的方程 : $F[n]=\min\limits_{i=1}^{n-1} F[i]+(h_n-h_i)^2+W[n]$

如果将 $h_n$ 当做变量，可以整理成 $(h_n^2+W[n])-2h_ih_n+(h_i^2+F[i])$

其中，前者是关于目标的常量，可不计，后面则是一个一次函数。

我们发现，这些一次函数的斜率不单增，因此不能仅仅使用单队维护。这里可以使用李超树。

李超树维护直线集合是 $O(\log n)$ 的，而且常数比平衡树小，还好写。

评测记录

CF932F Escape Through Leaf

设 $f[u]$ 为从 $u$ 点到达叶子的最小花费。

显然有转移 $f[u]=\min\limits_{\text{v在u的子树中}}f[v]+a_ub_v$ 。

我们可以把 $v$ 点的转移变成形如 $f(x)=b_vx+f[v]$ 的一次函数，每次代入 $a_u$ 求最小值。

这就可以使用李超树维护了。使用启发式合并，显然有复杂度 $O(n\log^2n)$ 。

实际上，直接线段树合并，先合并两棵子树，然后合并根节点信息，由于线段只会被下放，总复杂度是 $O(n\log n)$ 的。

评测记录

前缀最值相关 (兔队线段树)

P4198 楼房重建

题意 : 平面上有 $n$ 条线段 $(i,0),(i,H_i)$ 。

支持单点修改 $H_i$ ，查询从 $(0,0)$ 能看到多少条本质不同的线段。

先不考虑修改，尝试求出静态问题的答案。

显然，若楼顶被挡住，其他部分不可能被看见，所以我们只需要考虑楼顶。

计算出每个楼顶与 $(0,0)$ 连线的斜率，若某个楼顶的斜率比前面的都要大，则能被看见。

也即 : 斜率前缀严格最大值的个数。

考虑线段树维护，把某个区间当成完整的子问题。

$s[u]$ 为区间 $u$ 的前缀最大值个数， $mx[u]$ 为区间最大值。

在合并两个区间的时候，左边的最大值可能会把右边本来能看见的一部分楼房挡住。

设 $c\big([l,r],x\big)$ 表示 $[l,r]$ 区间中 $\geq x$ 的部分的前缀严格最大值的个数。

则合并 $[l,mid],(mid,r]$ 产生的前缀严格最大值的个数为 $s[lc]+c\big((mid,r],mx[lc]\big)$

考虑如何求出 $c$ ，可以直接利用线段树的信息来求解。

若到达叶节点，简单比较大小即可。

若 $mx[lc]<x$ ，左区间的贡献为 $0$ ，此时有 $c\big([l,r],x\big)=c\big((mid,r],x\big)$ 。

若 $mx[lc]\geq x$ ，则该点上记录的右侧前缀最大值必然均 $>x$ ，不必再次计算。

此时 $c\big([l,r],x\big)=s[u]+c\big([l,mid],x\big)-s[lc]$

不难发现上述算法总是只会递归一侧，复杂度是 $O(\log n)$ 的。

总复杂度为 $O(n\log^2n)$ 。

兔队指出，上述操作中涉及到了一个减法，若信息不满足可减性，则无法维护。

所以，考虑对各个区间 $u=[l,r]$ 改而维护 : 考虑整个 $[l,r]$ 时 $(mid,r]$ 内的前缀最大值数量。记为 $s'[u]$ 。

我们仍然沿用 $c\big([l,r],x\big)$ 的定义，则有：

$s[u]=c\big((mid,r],mx[lc]\big)$
$mx[lc]<x\Rightarrow c\big([l,r],x\big)=c\big((mid,r],x\big)$
$mx[lc]\geq x\Rightarrow c\big([l,r],x\big)=s[u]+c\big([l,mid],x\big)$

答案不能直接取用，可以使用 $c\big([1,n],0\big)$ 得到。

Seg-beats

有时候，题目中的操作会使信息量趋向于减小，此时可能产生均摊的做法。

前面的几道均摊小例题并非正统 Seg-beats 内容，较为熟悉的读者可以跳过。

P4145 上帝造题的七分钟2 / 花神游历各国

题意 : 给出一段长度为 $n$ 的序列，要求支持如下操作:

区间开根
查询区间和

大小为 $S$ 的正数在开根 $O(\log\log S)$ 次后会变为 $1$ 。 $0$ 开根总是 $0$ 。

我们在线段树上暴力 $dfs$ ，若发现某个区间内有大于 $1$ 的数才进入。

由于不会在中途停止，到达一次叶节点对应 $O(\log n)$ 的复杂度。

若到达叶节点，必然造成一次开根。总共的开根次数是 $O(n\log\log S)$ 次的。

总复杂度也就是 $O(n\log n\log\log S)$ 。

Loj#6029. 「雅礼集训 2017 Day1」市场

题意 : 给出一段长度为 $n$ 的序列，要求支持如下操作:

区间加
区间整除 $d$
询问区间 $\min$
询问区间和

接下来介绍一种典型的势能分析方法：容均摊。

即 : 找出一种能概括信息量的“特征值”，证明其消长和时间消耗有关，最终通过求和得到复杂度。

为了行文方便，下文将某节点点包含的信息复杂度称为“容”。

本题中，我们将一个节点的容定义为该节点内数字的极差。

若极差为 $0$ ，则代表所有的数字都相同，则可以批量操作并打下标记(可以转化成加法标记)。

若极差不为 $0$ ，则暴力递归下去。

一次除法操作显然可以至少让极差除以 $d$ 。对于某个节点，除 $O(\log S)$ 次就能让容变为 $0$ 。

任意的整体操作不会影响容的大小。

然而，一次“非整体”的任意修改操作会导致某个节点的容(不可预期地)变化。

一次区间操作最多提供 $O(\log n)$ 次“非整体”的修改操作。

也就是说，每次区间修改操作提供了 $O(\log n\log S)$ 的额外代价。

总复杂度 $O(n\log n+m\log n\log S)$ 。

然而，这是不严谨的，如果考虑下取整产生的误差，可能有除法之后极差不变的情况。

如 $5,6,5,6$ ，在除以 $3$ 之后变为 $2,3,2,3$ 加上 $3$ 之后又变回 $5,6,5,6$ 。

这样，每次除法操作都需要暴力，复杂度退化。

我们发现，下取整最多带来 $1$ 的偏差，所以极差为 $1$ 时才有可能除完极差不变。

我们只需要特殊处理极差为 $1$ 的情况，方法有很多。

最粗暴的方法就是记录此时两种数分别是什么，以及个数，不过这样不优美。

观察发现此时这两种数的加减变化量是相同的，我们可以在每次除法时判定，若区间内所有数除完之后加减变化量相同，则用加法标记代替。

提交记录

Uoj#228. 基础数据结构练习题

题意 : 在 P4145 的基础上，加入区间加操作。

类似地，我们将一个节点的容定义为该节点内数字的极差。

若极差不为 $0$ ，一次整体开根操作可以至少让极差开根。

证明 : 设原来的极差由 $x^2-y^2$ 产生，而开方后的极差为 $x-y$ ，由 $x^2-y^2=(x+y)(x-y)$ 且 $x+y\geq x-y$ ，不难推知 $x-y\leq \sqrt{x^2-y^2}$ 。

需要开根 $O(\log\log S)$ 次才能让容变回 $0$ 。每次区间修改操作提供了 $O(\log n\log\log S)$ 的额外代价。

总复杂度 $O(n\log n+m\log n\log\log S)$ 。

这同样是不严谨的，下取整仍然可以造成偏差，如 $3,4,3,4$ 开根之后变为 $1,2,1,2$ ,极差不变。

类似地应用加法标记即可规避。

提交记录

HDU5306. Gorgeous Sequence

题意 : 给出一段长度为 $n$ 的序列，要求支持如下操作:

区间对某个数取 $\min$
查询区间和
查询区间最大值

我们发现所有数值只会变小，即信息量减小。

考虑维护最大值 $mx$ ，最大值的个数 $cm$ ，以及严格次大值 $mx2$ ，区间和 $s$ .

对于一个修改 $y$ ，如果 $y\geq mx$ ，显然无影响。

如果 $mx>y>mx2$ ，那么只会对最大值产生影响，利用个数 $cm$ 来计算贡献，并打下标记。

如果 $mx2\geq y$ ，这次操作可能影响到最大值之外的数，我们无法在当前节点处理，只能向深处 dfs ，直到能处理为止。

复杂度看起来玄学，实际上是 $O((n+m)\log n)$ 的。

定义某个点的容为其中数的种类数。所有点的种类数和是 $O(n\log n)$ 的。

如果在 dfs 中需要经过，则至少会将该点最大值和次大值合并使得容减少 $1$ 。dfs的额外贡献就是 $O(n\log n)$ 的。

加入区间加操作

仍然考虑维护上述四个量 $mx,cm,mx2,s$ 。

把标记改进成 $(add,y)$ 的形式，意义为先加上 $add$ 再对 $y$ 取最小值。

取 $\min$ 修改时仍然按照上述规则大力 dfs。

根据论文中的证明，复杂度有上界 $O(n\log^2n)$ ，但实战中的表现近似于 $O(n\log n)$ 。

CF1290E Cartesian Tree

题意 : 给出一个排列 $P$ ，对于每个 $1\leq k\leq n$ ，询问当保留 $\leq k$ 的数时，该序列笛卡尔树(大根堆)的子树大小和。

首先分析一下性质，笛卡尔树的建树可以认为是每次抽取最大值分治。

那么，从 $i$ 出发，设左边第一个大于它的位置为 $pre[i]$ ，右边则为 $nxt[i]$ 。

那么， $pre[i],nxt[i]$ 一定比 $i$ 先选取，将 $i$ 与其他区域分隔开了。

现在， $i$ 是区间 $(pre[i],nxt[i])$ 最大值，那么整个区间一定都在其子树内。

这就证明了 $i$ 的子树大小是 $nxt[i]-pre[i]-1$ 。

令 $k$ 从小到大增加，维护 $nxt$ 和 $pre$ 的和即可求出答案。下面只讨论 $nxt$ 。

每次会增加一个比先存所有数更大的数，那么其会令左侧的 $nxt$ 对其位置取 $\min$ 。

但是注意，还空着的位置是不会计入下标的，我们其实是在 “插入”。

那么,右侧的所有标号都会增加 $1$ ,即对右侧的 $nxt$ 区间加 $1$ 。

区间取 $\min$ ，区间加，维护总和，直接套用上一题的做法即可。

还有一个要注意的是，由于我们在使用线段树，所以不可能真正的插入，而是预留好空位每次填掉。

这样以来，区间操作时，仍为空位的点需要被忽略。

使用维护点积的技巧，将空位的权设为 $0$ 即可。

提交记录

同时 $\min,\max$

题意 : ①区间对某数取 $\min$ 。②区间对某数取 $\max$ 。 ③查询区间和。

$\min,\max$ 夹来夹去，容终究还是会变小的，不会变大。

考虑再维护最小值，次小值然后讨论即可。复杂度仍然是 $O((n+m)\log n)$ 。

总结

上文的几个算法中，我们通过暴力 $\rm dfs$ ，把取 $\min,\max$ 这一操作，转化成了若干对最大值的加法操作。

我们可以对最大值和其他数分别维护两套标记。

维护两套标记的好处

题意 : 维护一个序列 $A$ ，支持 :

①区间对某数取 $\min$ 。②区间对某数取 $\max$ 。 ③区间加。

有另一个序列 $B$ ，如果某次修改中 $A_i$ 有变化，则 $B_i$ 加一。④询问 $B$ 的区间和。

如果是区间加操作，整个区间的 $A_i$ 都会改变，也就是 $B$ 都加一。

对于 $\min,\max$ 操作，转化为若干对最大/小值的加法操作，结合最大/小值个数，对 $B$ 的影响仍然容易算。

注意最大值和最小值可能相同，此时需要特判避免重复贡献。复杂度仍然是 $O(n\log^2n)$ 。

「二重奏」

题意 : 维护两个序列 $A,B$ ,资瓷

①将 $A$ 对 $x$ 区间取 $\min$ 。②将 $B$ 对 $x$ 区间取 $\min$ 。

③将 $A$ 区间加。 ④将 $B$ 区间加。 ⑤询问 $A_i+B_i$ 的区间最大值。

只有一个数组的时候，我们把值划分成最大值和次大值，现在有两个数组，我们可以进行类似的划分。

某个位置 : 同时为 $A,B$ 的最大值 / 只为 $A$ 的最大值 / 只为 $B$ 的最大值 / 其他数。

维护四套标记就好了。 $k$ 个数组则需要 $2^k$ 套标记。

历史值问题

历史值：在维护序列 $A$ 的同时，在每次操作后，序列 $A$ 会对序列 $B$ 的对应位置产生相应贡献。

历史版本和：每次操作后 $B_i\leftarrow B_i+A_i$ 。
历史最大值：每次操作后 $B_i=\max(B_i,A_i)$ 。
「线段树基础题」

题意 : ①区间加。 ③查询区间最大值。 ④查询区间历史最大值。

我们用标记来解决这类历史值问题。

在线段树标记的下推机制中，某个点存有标记，表示整一棵子树在标记存在的时间内都未曾更新。

于是，问题的核心就在于分析单个节点上停留的标记的影响。

在非历史值问题中，我们只关注该节点“当下”的标记是什么，所以我们会直接将标记合并起来。

但在历史值问题中，我们不仅要考虑该节点现在的标记合并结果，还要考虑历史上推来的（按时间为序的）每个标记的依次作用。

为了便于理解，我们不合并标记，假设每个节点上有一个队列（按照时间先进先出），放着所有曾经推过来的标记。

下推标记时，将该节点上所有的标记推到两个儿子处，并清空队列。

对于每个节点，维护 $x,m$ 分别表示 : 区间最值, 区间历史最值。

每次有一个区间加 $t$ 标记推来时，令 $x\leftarrow x+t$ 然后 $m\leftarrow \max(m,x)$ 。

这样做的正确性是显然的，但实际上我们不可能真的存下各个标记。

于是，我们寻找一种方法 概括一个队列的标记对当前节点的影响。

先思考对一个点打若干次标记的情形。

设推来的加法标记分别为 $t[1...k]$ ，其前缀和为 $S[1...k]$ 。

则打上第 $i$ 个标记之后， $x$ 的值为 $x+S[i]$ 。所以， $m$ 的值为 $\max_{i=0}^kx+S[i]=x+\max_{i=0}^kS[i]$

于是，只需记录 $\max_{i=0}^kS[i]$ 就能得知该标记队列对节点的影响。

合并加法标记的方法时简单求和，所以前 $i$ 个标记合并后恰好等于 $S[i]$ ，那么 $\max_{i=0}^kS[i]$ 可以表述为标记的历史最大值。

接下来考虑两个队列如何合并，设为 $t_1[1...k_1],t_2[1...k_2]$ ，合并后的结果为 $t_3[1...k_1+k_2]$ 。

注意到 $S_3[i]=\begin{cases}S_1[i]&(1\leq i\leq k_1)\\S_1[k_1]+S_2[i-k_1]&(k_1+1\leq i\leq k_1+k_2)\end{cases}$

我们需要快速得到 $\max_{i=0}^{k_1+k_2}S_3[i]=\max\Big(\max_{i=0}^{k_1}S_1[i],\ S_1[k_1]+\max_{i=0}^{k_2}S_2[i]\Big)$ 。

维护 $S_1[k_1]$ 即可，这也正是目前加法标记的值。

具体地，设 $t$ 为合并后的加法标记， $mt$ 为加法标记的历史最大值。

每次 $u\rightarrow v$ 下推的时候,令:

v.m=max(v.m,v.x+u.mt);
v.mt=max(v.mt,u.mt+v.t);
v.x+=u.t;
v.t+=u.t;
u.t=u.mt=0;

P4314 CPU监控

题意 : ①区间加。 ②区间赋值。 ③查询区间最大值。 ④查询区间历史最大值。

原来曾经是黑题，现在因为技巧进一步普及，掉紫了。

若不考虑赋值操作，则转化为上一题。下面考虑赋值操作。

在经典线段树题目中，偶尔可以不思考两个标记的互相作用，直接令两个标记互斥。

然而，在维护历史版本的线段树问题中，需要完整地考虑每个标记的历史影响，则不能采用这种手段。

现在在我们的标记队列中，存在两种标记。两种标记混杂的情况并不便于处理。

可以发现，若存在一个赋值标记，则之后整个区间都是同一个数，那么加法标记可以等价地转化为赋值标记。

于是，该标记队列等价于一个加法标记队列紧跟着一个赋值标记队列。加法标记队列用前文的方法处置。

对于赋值操作 $c[1...k]$ ，最终产生的历史最大值为 $\max_{i=1}^kc[i]$ ，记录下这个即可。意义为“赋值标记的历史最大值”。

具体操作可见代码。

P6242 【模板】线段树 3

使用 $\rm Seg-beats$ 维护 $A$ 的区间和。

把区间取 $\max$ 划分成若干对区间最大值的加法操作。

我们维护两套标记，一套只对最大值生效，另一套对所有数都生效。

注意，只对最大值生效的标记下推时要判断儿子是否含有同样的最大值。

历史最大值的合并是要讲究顺序关系的（因为标记队列是有顺序的），所以标记影响的对象必须不交才方便维护。（难以处理多个标记队列）

所以，我们让另一套标记对最大值之外的数（而非所有数）生效。

有若干坑点 :

判断儿子是否含有最大值时，要在两个儿子之间比较。
若儿子不含有最大值，需要对其（略小的）最大值打上对非最大值生效标记。

具体细节见代码。

历史版本和

记原序列为 $A$ ，版本和序列为 $B$ 。

可以把 “更新 $B$ 序列”也看作一种标记，每次操作后给整棵树打一个。

考虑一个更新标记和加法标记交替出现的队列，记当前节点区间和为 $s$ ，历史版本和为 $ms$ ，区间长度为 $len$ 。

加法标记 $t$ 会令 $s\leftarrow s+t*len$ 。更新标记会使得 $ms\leftarrow ms+s$ 。

考虑标记队列 $q[1...m]=\{t_1,t_2,upd,t_4,upd...\}$

记 $S_t[i]$ 为前 $i$ 个标记中，加法标记的和。

则对 $ms$ 的总贡献为 $\sum\limits_{i=1}^{k}\big[q[i]=upd\big]s+S_t[i]*len=s\Big(\sum\limits_{i=1}^{k}\big[q[i]=upd\big]\Big)+len*\sum\limits_{i=1}^{k}\big[q[i]=upd\big]S_t[i]$

于是，我们只需记录 $\sum\limits_{i=1}^{k}\big[q[i]=upd\big]$ 和 $\sum\limits_{i=1}^{k}\big[q[i]=upd\big]S_t[i]$ 。

意义是更新标记的总个数，以及每个更新标记打上时， $S_t[i]$ 的和，即加法标记的历史版本和。

若两个队列 $q_1,q_2$ 拼接得到 $q_3$ ，更新标记的总个数容易计算。

$$\begin{aligned} &\sum\limits_{i=1}^{|q_1|+|q_2|}\big[q_3[i]=upd\big]{S_3}_t[i]\\ =&\sum\limits_{i=1}^{|q_1|}\big[q_1[i]=upd\big]{S_1}_t[i]+\sum\limits_{i=1}^{|q_2|}\big[q_2[i]=upd\big]{S_2}_t[i]+{S_1}_t[|q_1|]\\ =&{S_1}_t[|q_1|]\Big(\sum\limits_{i=1}^{|q_2|}\big[q_2[i]=upd\big]\Big)+\sum\limits_{i=1}^{|q_1|}\big[q_1[i]=upd\big]{S_1}_t[i]+\sum\limits_{i=1}^{|q_2|}\big[q_2[i]=upd\big]{S_2}_t[i]\\ \end{aligned}$$

于是，再记录 $S_t[|q|]$ 即合并后的加法标记，则可以合并。

具体地，设 $t$ 为加法标记， $mt$ 为加法标记的历史版本和， $upd$ 为更新标记个数。

当 $u\rightarrow v$ 更新时。

v.ms+= u.upd*v.s + u.mt*v.len;
v.mt+= v.tg*u.upd + u.mt;
v.upd+= u.upd;
v.s+= u.tg*v.len;
v.tg+= u.tg;

[DS记录]P3246 [HNOI2016]序列
[DS记录]CF997E Good Subsegments
$\rm Arithmetic$

题意：一个多重集合的价值定义：将其变为公差为 $d$ (给定常数) 的等差数列需要插入几个数字（无法实现则价值为 $0$ ）。

多次询问 $[l,r]$ 的子区间的价值和。

若可以变为公差为 $d$ 的等差数列，则称该区间合法。

不难发现，若区间 $[l,r]$ 合法，那么其所有子区间都合法。

我们从每个右端点 $l$ 找到最靠左的 $r$ （这可以双指针求出），所有这些极长区间的子区间的并集就是所有合法的区间。

对于一个合法的区间 $[l,r]$ ，其价值容易计算： $(\max-\min)/d-(r-l)$

考虑离线，从左到右移动右端点，并维护每个左端点对应的答案。

当 $r$ 增加时，首先要删掉不合法的部分，这里可以暴力单点删除。

接下来，分别维护 $\sum \max ,\sum \min ,\sum l,\sum r$ 。

$\sum l$ 和 $\sum r$ 比较显然。前者相对下标不变，可以在双指针移动时处理。后者则每移动一次 $r$ 触发 $+1$ 。

$\sum \min$ 和 $\sum \max$ 是类似的，只讨论后者。

维护单调栈，栈中两个元素之间的左端点对应的 $\max$ 是相同的，贡献可以看做区间加。

而单调栈的变化次数时均摊 $O(n)$ 的，则会产生 $O(n)$ 个区间加法。

将右端点移动到 $r$ 时维护左端点的线段树状态称为版本 $r$ 。

设 $v(l,r)$ 为区间 $[l,r]$ 的价值。

若我们需要求出 $\sum\limits_{i=l}^rv(i,r)$ ,则在版本 $r$ 做区间求和即可。

我们要求是 $\sum\limits_{i=l}^r\sum\limits_{j=l}^rv(i,j)$ 则要在 $l...r$ 版本同时做区间求和，不难转化成历史版本和问题。

将线段树可持久化可以支持强制在线。

Uoj#164. 【清华集训2015】V

题意 : ①区间减 $x$ 并对 $0$ 取 $\max$ 。 ②区间加。 ③区间赋值。

④单点查询。 ⑤单点查询历史最大值。

可以设计出一种标记 $(add,y)$ ,表示先加 $add$ 再对 $y$ 取 $\max$ .

不难发现题目中的所有操作都可以用这个标记描述 : ① $(-x,0)$ ，② $(x,-\inf)$ ，③ $(-\inf,x)$ 。

标记合并的时候,原有 $(a,b)$ 与 $(a_2,b_2)$ 合并,则变为 $(a+a_2,\max(b+a_2,b_2))$ 。

现在考虑历史最大值如何维护。由于是单点查询，只需把标记推到叶子，我们只需要对标记做手脚。

历史最大值实际上就是标记前缀和的 $\max$ 。只要能求 $\max$ ，和前面的题目维护方法是相同的。

按照值域考虑每个数接受标记之后会变成什么,发现是一个如下图所示的折线:

(讲到这里,人人都要画一样的图,我就剻了个图来, $\text{stO灵梦}$ )

两个标记的 $\max$ 就是这两个函数的 $\max$ 。不难发现 $\max\big((a,b),(c,d)\big)=\big(\max(a,c),\max(b,d)\big)$。

让最终的标记对叶节点的数作用一次,则得到答案。

提交记录

Uoj#515. 【UR #19】前进四

题意 : 单点修改，询问 $a_x,⋯,a_n$ 的不同的后缀最小值个数。允许离线。

可以直接沿用「楼房重建」的做法，然而复杂度 $O(n\log^2n)$ 太差，无法获得满分。

注意到每次询问的都是后缀，而且可以离线，考虑如何利用这两条性质。

有如下暴力 : 从末尾向前扫，求出后缀最大值，若其改变则答案 $+1$ 。

可以按数组下标从后向前扫，以时间为下标，设枚举到第 $k$ 个位置， $t_{k}[i]$ 表示当前位置在第 $i$ 个时刻的后缀最大值。

我们发现，某个修改操作的影响，是给某个时间区间 (该次修改生效的区间) 取 $\min$ 。

查询相当于问某个位置被更改过多少次，不难使用数域划分后的历史版本和标记维护。

具体实现中，对于一个针对最大值的标记，需要记录标记本身被修改的次数。

非常卡常，这可能是差评数量多的原因吧……具体技巧见代码。

提交记录

Uoj#169. 【UR #11】元旦老人与数列

题意 : ①区间加。 ②区间取 $\max$ 。③查询区间最小值。 ④查询区间历史最小值。

此时若沿用标记 $(add,y)$ ，则合并时要对标记取 $\min$ ,就发生了下面的事:

可以看到我们并没有让信息量减少。

考虑转而使用容均摊数域划分，变为若干个给最大值的加法操作，就易于维护了。

提交记录

关于线段树上的一些进阶操作

前言

杂项

线段树合并

李超线段树

前缀最值相关 (兔队线段树)

Seg-beats

历史值问题

状态

开发

支持

关于

还没有账户？

登录