区间最值操作 & 区间历史最值

· · 算法·理论

区间最值操作与区间历史最值详解 - 灵梦

《区间最值操作与历史最值问题》- 吉如一

线段树维护历史版本和 - Spaseeker

U216697 线段树区间历史版本和

区间最值，区间加的复杂度证明：

考虑标记为所有线段树节点中，子树 \min \ne 父亲的子树 \min 的节点，打上标记为子树 \min。势能为整棵线段树的标记个数。

区间取 \max 和区间加，只有 \Theta(\log n) 个拆分区间的标记可能更改（对于 \max，如果递归到子树内，则是删除标记；否则对区间 \min 加不会影响标记个数）

而删除一个标记需要 \mathcal{O}(\log n) 次递归。总复杂度 \mathcal{O}((n+m\log n)\log n)。

《区间最值操作与历史最值问题》（吉如一）阅读笔记 - kyEEcccccc

线段树维护的是双半群信息：

$M$ 表示标记的半群； 那么有三种操作： 1. 将值合并 $D+D \to D$； 1. 将标记应用到值上 $D\times M \to D$； 1. 将标记复合 $M * M \to M$； --- 由于加法标记设置在覆盖标记之前，所以当标记复合的时候，新标记的加法操作应该根据旧标记的覆盖操作，**将已经确定的常数项根据下传标记的定义分配到更低次幂的增量上。** ### 区间加；区间赋值；查询区间历史版本和 将标记视为一次函数：即最后对历史版本和的贡献为： $k \times t + b

对于赋值操作，相当于把一次函数截断。

那么对于一个标记（序列），维护开头到第一次赋值的 k,b,t，最后一次赋值之后的 k,b,t，可以支持合并。