吉老师线段树

概述

• 所谓吉老师线段树，指的其实是吉如一发明/整理的线段树上区间最值操作和区间历史最值的维护方式。

操作

区间最值操作

• \(\forall i\in[l,r],a_i=\min/\max(a_i,v)\)。

区间历史最值

• 历史最大/小值：定义序列 \(b_{1\sim n}\)，每次操作后，令 \(\forall i\in [1,n],b_i=\min/\max(b_i,a_i)\)。

• 历史版本和：定义序列 \(b_{1\sim n}\)，每次操作后，令 \(\forall i\in [1,n],b_i=b_i+a_i\)。

• 应当指出的是，本篇中认为吉老师线段树的默认环境是大一统环境，即除上述特色操作和询问外，有加、减、乘、赋值操作，有最值、求和询问，实现也是基于此的（如果没有某些操作/询问，可能并不需要这么麻烦的实现）。

复杂度分析

• 仅一种区间最值操作时，复杂度为严格 \(O(n\log)\)。这里认为 \(n,Q\) 同阶，后略。

• 若不止一种区间最值，或与区间赋值/加减乘等经典操作相结合，则复杂度为 \(O(n\log^2)\)，但实际实践表明其很可能是 \(\Theta(n\log)\)，可以认为其是 \(O(n\log)\)。

实现原理

区间最值操作

• 我们以 \(chkmin\) 操作为例，\(chkmax\) 操作对称处理即可。

• 考察朴素线段树的区间修改，其依赖于两点：

  1. 区间整体价值的可快速计算性。

  2. 懒标记的可合并性。

• 显然 \(chkmin\) 操作满足第二条，但不满足第一条，朴素的区间修改方式并不能达到效果（赋值操作乍一看也不满足第一条，但事实上可以暴力重构区间整体价值，而非贡献法）。

• 我们转而考虑进行值域分段，将 \(chkmin\) 操作转化为减操作。具体来讲，我们在线段树节点上维护最大值 \(mx\)，严格次大值 \(se\) 和最大值个数 \(cntmx\)。当然，\(sum\) 等常规信息也是要维护的。

• 记当前我们要对 \([L,R]\) 做 \(chkmin(v)\)。首先我们如普通线段树的区间修改操作一般进行区间下放，过程中如果 \(mx\leqslant v\) 则直接返回，否则完成下放过程。

• 对每个到达区间，我们分类讨论：

  1. \(mx\leqslant v\)。事实上这种情况在刚才就返回了。

  2. \(se<v<mx\)。显然本次修改只会影响到最大值，我们令 \(sum=sum-(mx-v)\times cnt_{mx}\)，然后 \(mx=v\)，并打上 \(lz=v\) 的标记，其他信息不变，显然这是对的。

  3. 当 \(v\leqslant se\) 时，无法直接更新此节点的信息，进一步递归。

  4. \(v<mx\)，且 \(se\) 不存在。相当于第二种情况。

复杂度证明

单最值操作环境

• 首先我们对这种维护方式做以一定的转化。

• 定义 \(tag_x\) 为线段树节点 \(x\) 的最大值即 \(mx_x\)。然后若 \(tag_x=tag_{fa_x}\)，删去 \(x\) 处的标记，注意这一过程是自底向上的。

• 则现在标记有如下几个性质：

  1. 一条祖孙链上的标记互不相同。不妨假设 \(u\) 为 \(v\) 的祖先，若它们的标记相同，由性质 3 的 \(\geqslant\) 部分（此部分的证明不依赖本条性质）可以推出删标记前 \(u\to v\) 路径上的标记全部相同，于是应当 \(v\) 被擦掉。

  2. 至多只有 \(n\) 个。不妨认为 \(x\) 处有标记，记其来源为 \(y\)，则 \(x\to y\) 的链上除 \(x\) 之外的点都不应有标记，又最后一层只有 \(n\) 个点，所以至多只有 \(n\) 个标记。

  3. \(\forall y\in sub_x,tag_x>tag_y\)。显然，否则 \(x\) 子树内的最大值不小于 \(tag_y\)。于是 \(tag_x\geqslant tag_y\)，又由性质 1，\(tag_x>tag_y\)。

  4. \(a_i\) 的值相当于 \(lf_i\to rt\) 上的第一个标记的值。显然当标记在 \(lf_i\) 上时成立，从而当标记在 \(fa_{lf_i}\) 上时，由 \(lf_i\) 上没有标记，应有 \(tag_{fa_{lf_i}}=tag_{lf_i}=a_i\)，归纳可证本性质成立。

  5. \(se\) 相当于除 \(x\) 外，\(x\) 子树内的 \(tag\) 最大值。显然，其实可以由性质 3 推出。

• 于是，我们的操作可以认为是：

  1. 找到对应区间，如果 \(mx\leqslant v\) 则返回，否则在对应节点打一个 \(tag=v\)。

  2. 维护性质。事实上，只要回收掉子树内 \(\geqslant v\) 的标记，就等价于这一目的。这一问题比较复杂，我们详细谈谈：

  • 关于性质 2 的维护：性质 2 是归纳的，或者说归纳证明的性质 2 对我们更有利。先给性质 2 加一个“根上一定有 \(tag\)”。

  • 显然当 \(n=1\) 时性质 2 成立，进一步考虑把左右子树拼起来加个 \(fa\)，显然 \(tag_{fa}=tag_{ls}\) 和 \(tag_{fa}=tag_{rs}\) 至少成立一个，于是两者至少擦一个，于是归纳得证。

  • 性质 2 可能不能在子树内维护完全，但可以在子树内维护到对子树成立。而返回时的 pushup 会保证对更大子树成立。

  • 充分性：

    1. 若改完后相同，则说明 \(v\leqslant se\)，于是递归，递归证明到 \(n=1\)，显然 \(n=1\) 不可能有 \(v\leqslant se\) 也即不相同，得证。

    2. 打了标记说明 \(mx>v\)，那么本来的标记是 \(mx\)，现在换了，得证。

    3. 若 \(\leqslant\)，则 \(v\leqslant se\)，递归到 \(n=1\)，同性质 1，得证。

    4. 只有原本 \(a_i>v\) 的会受影响，同性质 2。

    5. 和性质 2 一样是子树归纳的，可以由其他性质推出，略。

  • 必要性：维护过程中，\(tag<v\) 相关信息显然不变，从而等价于回收 \(\geqslant v\) 的标记，且一定是删了或者换了更小的，否则还得维护，不满足性质 3。

• 然后我们定义标记类：

  1. 一次 \(chkmin\) 产生的标记是同一类。

  2. 同一个标记下传产生的标记是同一类。

  3. 不满足前两个条件的标记属于不同类。

• 定义标记类 \(\alpha\) 的权值为这一类标记连同线段树的根对应的虚树大小，记为 \(\phi(\alpha)\)，定义势函数 \(\Phi(sta)=\sum\limits_\alpha \phi(\alpha)\)。我们进行如下的势能分析：

  • 考虑区间下放和打 \(tag\) 对势函数的影响。显然，到达点只有 \(O(\log)\)，增加 \(O(\log)\) 个 \(tag\)，即势函数只增加 \(O(\log)\)。证明在朴素线段树的区间操作处已经做过了。

  • 考虑标记下推，显然只有 \(\phi(\alpha)\) 被增加了 \(1\)。

  • 考虑进一步递归对势函数的影响。由上面的证明，我们知道递归的所有到达点 \(x\) 都满足 \(tag_x\geqslant v\)，从而访问到的所有点都 \(tag_x\geqslant v\)（由性质 2）...这一步有问题。

  • 但至少我们可以证明，进一步递归每至多跑满一条链即花费至多 \(O(\log)\) 的代价，就让势函数 \(-1\)。这对应着一个 \(O(n\log^2)\) 的宽松上界。

  • 事实上可以证明进一步递归中每访问一个点就让势函数 \(-1\)，于是摊还复杂度为 \(O(n\log)\)。

• 综上，修改操作中势函数的总变化量为 \(O(n\log)\)，初始时的势函数至多为 \(O(n)\)，因为 \(k\) 个点的虚树只有至多 \(2k-1\) 个点（证明见虚树），进一步递归之前的总复杂度也为 \(O(n\log)\)，故总复杂度为 \(O(n\log)\)，单次操作均摊 \(O(\log)\)。

复杂环境

• 显然标记类不再能沿用，因为区间加减会改变它（不谈区间赋值，区间赋值在标记类上甚至弱于 \(chkmin\)）。

• 但可以修定义：一次区间加减若碰到了某一类标记的一部分，则该类标记分裂为两类；否则该类标记不变。

• 我们把线段树的根从虚树里扔进去。我的意思是，不再额外加进来。

• ...蚌，证不下去，没有充分理解。就算硬凑完，也是 \(O(n\log^3)\)。倒是有一个 promising 的，论文中提到的另一个方向：定义势函数为标记深度和。