一些背景和定义
在数据结构题中，有一些问题的询问是关于历史版本的，除了大部分考察可持久化数据结构的问题，剩下一类特殊的问题被称为“历史最值问题”。
历史最值问题的询问通常与“历史最大值”、“历史最小值”、“历史版本和”有关，而此时相应地包含名为“扩展版本”的修改。
值得一提的是，相当一部分题目是在每一次对原序列的修改后都执行一次“扩展版本”，下文中若无特殊提及“扩展版本”，就默认是此类情况；否则会说“动态扩展版本”。
它们的形式化定义是什么？
让我们定义辅助数组 \(B\)，而令题目中直接修改的数组为 \(A\)。
对于历史最大值、历史最小值，一开始 \(B = A\)；对于历史版本和问题，一开始 \(B=0\)。
每次“扩展版本”时，我们令 \(B_i \leftarrow \max(B_i, A_i) \ \text{or} \ \min(B_i, A_i) \ \text{or} \ B_i + A_i\)，对应的分别是“历史最大值”、“历史最小值”和“历史版本和”。
此时我们的询问就是基于 \(B\) 数组的。
关于历史最值问题，可以通过处理方法的不同，从易到难划分为四种情况，接下来会按顺序介绍。
懒标记可以处理的问题
在此类问题中，我们会使用带懒标记的线段树解决。
设计节点信息和标记
首先节点信息和普通的线段树节点信息设计是一样的——不断把合并要用到的辅助信息加入即可。接下来我们讨论的都是标记的设计。
我们可以假设在线段树的每个节点上有一个隐式的标记队列，此时标记是不合并的，只会在修改时加入对应节点的队列，或下传标记时把当前节点的队列分别合并到两个子结点的队列后面，再清空当前节点的队列。
直接应用这种做法虽然能从正确性上解决问题，但时间复杂度是不能接受的。
因此，我们寻求这个标记队列的一个概括，这也就是我们最终的懒标记，它需要满足以下要求：
- 在修改时，新的标记可以快速和已有的概括合并。
- 在下传时，概括能够快速合并，并且概括的信息形式是封闭的（封闭是指不需要其他的辅助信息就可以进行合并）。
- 概括没有丢失更新节点信息需要的关键值。
大致上，我们可以通过对单个标记对节点信息的贡献进行复合，并提取最终式的特征值。最后再像维护节点信息那样不断加入合并用到的辅助信息。
来几道例题感知一下。
试试看
线段树基础题 from cmd's blog
区间加，查询区间历史最大值。
解答
节点信息：最大值 \(x\)，历史最大值 \(m\)。
标记队列里只有加法标记，考虑一个 \(+k\) 对最终答案的影响：
- \(x \leftarrow x + k\)，\(m \leftarrow \max(m, x)\)
那么我们把所有的单标记贡献求和（因为贡献的形式是加法），有：
其中 \(pre\) 为 \(k\) 的前缀和。
令概括为 \(\max_{i=0}^q pre_i\) 和 \(\sum_{i=1}^q k_i\) 即可，容易发现此时形式封闭，读者不难自行验证。
铃原露露（改）
区间加，动态扩展版本，查询区间历史最小值个数。
解答
节点信息：最小值 \(mn\)，最小值个数 \(cnt\)，历史最小值 \(hmn\)，历史最小值个数 \(ans\)。
标记队列里有加法标记和扩展版本的标记，我们不好分析多种标记的情况如何概括，因此考虑转化。
容易发现在两次扩展版本标记之间的加法标记可以被缩成一次（简单把加法标记的值加起来就好了），因为中间没有扩展版本标记，就不会中途造成贡献。
我们记录 \(k_i\) 表示第 \(i - 1\) 个扩展版本标记和第 \(i\) 个扩展版本标记之间的加法标记缩成了什么值。
那么对于每个 \(k_i\) 仍有：
- \(mn \leftarrow mn + k_i\)，\(hmn \leftarrow \min(hmn, mn)\)
- \(ans \leftarrow ans + [hmn = mn]cnt\)
对于所有的 \(k_i\) 复合贡献，可以得到：
因此我们只需要在概括中记录 \(\sum_i k_i\)，\(\min_i pre_i\)，\(\sum_j[pre_j = \min_i pre_i]\) 即可，即标记之和、标记的前缀最小值 和 标记的前缀最小值个数。容易验证这是封闭的。
CPU监控
区间加，区间赋值，查询区间历史最大值。
解答
节点信息：最大值和历史最大值。
此时我们的队列里既有赋值标记也有加法标记，跟上题一样，这是我们不愿意见到的。因此考虑转化。
容易发现，一个赋值标记后连续的加法标记都可以看作赋值标记！比如标记 \(=x\) 后面有标记 \(+y\)，把标记 \(+y\) 看作标记 \(= x + y\) 即可。
这样，我们的队列就可以被分成两部分，连续的一段前缀都是加法标记，连续的一段后缀都是赋值标记。
与 线段树基础题 from cmd's blog 类似概括即可，只需要多记录后面赋值标记的 \(\max\) 这个信息就可以封闭。
这里举的几个例子仅为了感知构建概括的逻辑。优秀的题目还有很多，Reference（在文末）的两篇文章中均提到了更多的习题。
无法用懒标记处理的一般问题
此类问题通常在一般操作的基础上还含有区间最值操作。而吉司机线段树可以以均摊一个 \(\log\) 的代价把区间最值操作变为对区间最值的加减操作。
在此基础上，我们人为把每个节点的最值和非最值区分开来，也就是为每个节点维护两个概括（一个作用于最值，一个作用于非最值），这样就可以完成此类问题。
无区间最值操作的历史和问题
注意！此处的“历史和”和先前提到的“历史版本和”是不同的定义。
历史和问题大多都是询问 \(\sum B_i\)（\(B_i\) 是单点的历史最大值或历史最小值或历史版本和）。
对于历史和问题，我们是通过转化（定义辅助数组）完成的。
注意，像区间赋值这样的操作属于第一类历史和问题（如 NOIp 2022 T4 比赛），这里无法支持区间赋值，只能支持变化量固定的操作。
下面都以区间加修改为例。
历史最大值的和
定义 \(C_i = A_i - B_i\)（对每一时刻都成立），当我们查询 \(\sum_{i=l}^r B_i\) 时，我们只要查询 \(\sum_{i = l}^r C_i\) 和 \(\sum_{i=l}^r A_i\) 就可以了。
\(A_i\) 的维护就是普通线段树能完成的，那么我们如何维护 \(C_i\)？
从定义上说，如果我们对 \(A_i + x\)，那么新的 \(B_i \leftarrow \max(B_i, A_i + x)\)。
故新的 \(C_i \leftarrow A_i + x - \max(B_i, A_i + x) = \min(A_i - B_i + x, 0) = \min(C_i + x, 0)\)。
故我们先区间加再对区间 checkmin，这是吉司机线段树可以完成的。
历史最小值的和
与历史最大值的和类似，维护 \(C_i = A_i - B_i\)，每次相当于 \(C_i = \max(C_i + x, 0)\)。
我们先区间加再区间 checkmax，也是吉司机线段树可以完成的。
历史版本和的和
设 \(t\) 为当前的时刻（当前操作前的操作数），定义 \(C_i = B_i - t A_i\)。
假设一次操作后 \(A_i \leftarrow A_i + x\)，那么 \(B_i \leftarrow B_i + A_i + x\)（此处的 \(A_i\) 是修改前的）。
故 \(C_i \leftarrow B_i + A_i + x - (t+1)(A_i + x) = B_i - t A_i - t x = C_i - t x\)。
因此 \(A_i\) 区间加 \(x\)，\(C_i\) 就区间减 \(tx\)，这是普通线段树就能维护的。
有区间最值操作的区间和问题
把第二类和第三类的做法拼一起！
我们通过支付一个 \(\log\) 的代价变为区间加减最值。
然后对于区间的最值和非最值分开做第三类问题即可。
扩展
吉司机线段树的一些问题是可以对多个（假设 \(k\) 个）数组做的。
此时我们对于每个数组都区分最值和非最值，时间复杂度大概 \(\mathcal O(2^k \times t)\)（\(t\) 为原问题复杂度）。
Reference
- 吉如一《区间最值操作与历史最值问题》
- command_block《关于线段树上的一些进阶操作》