[数据结构] 线段树历史信息维护

· · 个人记录

感觉线段树维护历史信息的题做完就忘 /yun……于是开篇文章记录下

本文认为 n,m 同阶，mx,hmx,sum,hs,,A,t 分别为区间最大值、历史最大值、和、历史和、加法操作、累加操作（具体意义下文还会解释）。

主要思路

线段树的维护需要考虑三个方面

其中第一点就是 push_up 函数，在这类题中一般都是平凡的，不再赘述。

关键在于最后两点，将每个节点上覆盖的按时间排序的操作序列提取出来，我们的目标就是将这一段 O(n) 长度的操作序列用 O(1) 个 tag 描述出来（其实就是懒标记），并且能做到正确地合并两个节点的操作序列以及对节点信息的更新，也就是 push_down 函数。

1. 历史最值

先来一道练手题：SP2916

一道经典的区间非空最大子段和的一眼题，线段树节点维护最大前后缀以及最大子段和即可。

不过这里我想提出来另一种非空最大子段和做法：区间加，区间维护历史最大值。我才不会说我是因为脑梗没看出来维护最大子段和所以用维护历史最值方法做的

将序列做前缀和，不难发现询问 [l,r] 就是求 \max_{l \le i < j \le r}(sum_{j} - sum_{i})，将右端点作为横轴，左端点作为纵轴，那么坐标系中每一个点 (x,y) 就对应了一个原序列的一个子段 [x,y]，将该点的的权值设为 sum_{y}-sum_{x-1} （如果 x>y 则为 -\inf），那么对于一个询问，我们求的就是下图中的红色三角形部分的最大值，因为有 -\inf， 所以直接扫描线，区间加维护扫描线上的值，求区间历史最大值即可，下面具体讲解一下如何维护：

首先肯定要对每个线段树节点维护区间最值和区间历史最值两个值，然后考虑怎样描述一个节点上的操作序列，假设当前节点有操作序列：

A_{1},A_{2},A_{3}...A_{k}

假如我们只用序列的和来描述的话，当我们下传该序列接到儿子的序列之后时就会发现我们无法更新儿子的历史最大值了，因为实际上可能是在某一时刻 t(t<k)而不是在 k，mx+{\textstyle \sum_{i=1}^{t}}A_{i} 取得了最大值，导致 hmx 偏小。

那么此时正解就十分显然了，除了维护 \sum A_{i}，我们再维护一个前缀最大值 hadd，push_down 时执行 hmx \gets \max(hmx,mx+hadd) 即可正确维护。

代码（实现上这种类型只需要改一下 push_down 即可）

习题（有题再加）：

2、历史版本和

考虑加上区间累加操作 t，表示将 sum 累加到 hs 上 t 次，对于一个操作序列（相邻同类型操作已经合并）：

A_{1},t_{1},A_{2},t_{2},A_{3},t_{3}...

考虑用 sa,st （分别表示 \sum A_{i}, \sum t_{i}）描述这个序列，下放时 sum \gets sum+len \times sa、hs \gets hs+sum \times st。 但这样显然会多算，比如 A_{3} 多算了 t_{1} + t_{2} 次，这时候再维护一个 tag hadd 用来表示多算的贡献，每次向序列后加入一个 A 时，hadd \gets hadd + st \times A 即可。

习题（有题再加）：

语言没有怎么仔细打磨，哪里讲得不清楚还请指出QAQ，反正未来的我能看懂就行（逃