专栏文章

历史和线段树

DDE_aemmprty
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mink5y33
此快照首次捕获于
2025/12/02 03:44
3 个月前
此快照最后确认于
2025/12/02 03:44
3 个月前
查看原文
我们一般在处理区间修改的操作时，会在线段树上打懒标记，意思是这个结点所代表的区间中的所有数都要同时进行一系列修改。为了更容易理解历史和线段树，我们先来回顾一下普通线段树的区间加操作。

Preperation\mathbf{Preperation}

引理

对于区间加，区间求和问题，我们在做线段树时，有结论：子节点的懒标记时间比父节点的懒标记靠前。
我们把注意力放在父子结点的懒标记之间的时间关系上，我们发现，操作后，新的被打上标记的顶点 tt，它的父亲节点的标记都被下放了，所以父亲结点的懒坐标只可能在之后出现。

Part.1\mathbf{Part. 1}

进入正题。
给你一个序列 a1a_1 到 ana_n，初始全为 00。你需要支持如下操作：
  • 将 [l,r][l, r] 区间中的每个数 aia_i 加上 yy
  • 查询 [l,r][l, r] 在历史每个时刻的和的总和
容易想到每次修改的时候，我们对 [l,r][l, r] 的 aia_i 区间加。然后，我们在全局上打一个历史和更新的标记。
我们对每个结点，记录三个信息，分别是 his,sum,len\texttt{his}, \texttt{sum}, \texttt{len}，表示这个区间的历史和，区间和，区间长度。由引理，我们知道在下放懒标记和单点加标记的时候，可以视作一些懒标记在前，一些懒标记在后，现在要合并在一起。
但这没有只有加法标记的时候那么显然，因为现在还有一个历史和更新操作，不是很好合并。
下文介绍两种方法。（还有一种我觉得不涉及历史和线段树的思想，不在赘述）

Part.1.1 Matrix\mathbf{Part. 1.1 \ Matrix}

我们考虑刻画这两种标记分别在对这三个信息做什么。
  • 区间加标记 vv：sum=sum+len×v\texttt{sum} = \texttt{sum} + \texttt{len} \times v
  • 历史和更新标记：his=his+sum\texttt{his} = \texttt{his} + \texttt{sum}
实际上，这两种标记都只是在这三个变量里做线性变换，因此考虑用矩阵刻画。
我们把要存储的信息全部列在矩阵里，也就是 [hissumlen]\begin{bmatrix}\texttt{his}\\\texttt{sum}\\\texttt{len}\end{bmatrix}，那么有：
  • 区间加标记 vv：乘上 [10001v001]\begin{bmatrix}1 & 0 & 0 \\0 & 1 & v\\0 & 0 & 1\end{bmatrix}
  • 历史和更新标记：乘上 [110010001]\begin{bmatrix}1 & 1 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}
现在，标记的合并都被刻画成了矩阵乘法，于是就十分好做了。

Part.1.2 Tag Queue\mathbf{Part. 1.2 \ Tag \ Queue}

我们直接考虑如何合并两个标记队列。假设有两个标记队列 A,BA, B，AA 在前，BB 在后。我们先把只在 AA 或者 BB 内的贡献加起来，计这个内部贡献为 retret。那么，我们只需要计算两个标记队列之间的贡献即可。
对于 AA 队列里的任意一个加法标记，它在 BB 每次历史和更新时都会被算一次，因此两边之间的贡献就是 addA×updB\texttt{add}_A \times \texttt{upd}_B，其中 addA\texttt{add}_A 表示 AA 中的加法标记和，updB\texttt{upd}_B 表示 BB 中的历史和更新标记个数。
我们对每个结点，再计三个数 add,upd,ret\texttt{add}, \texttt{upd}, \texttt{ret} ，用来表示整个标记队列。那么我们考虑一次下放操作，有 sum=sum+add′\texttt{sum} = \texttt{sum} + \texttt{add}'，ret=ret+ret′+add×upd′\texttt{ret} = \texttt{ret} + \texttt{ret}' + \texttt{add} \times \texttt{upd}'，add=add+add′\texttt{add} = \texttt{add} + \texttt{add}'，upd=upd+upd′\texttt{upd} = \texttt{upd} + \texttt{upd}'。根据这个转移即可。
我们比较一下这两种方法。
  • 矩阵计 tag 适用性十分高，因为只需要你的操作都是线性变换，就可以用矩阵做。但缺点是常数比较大。
  • 暴力考虑标记序列合并，其实相当于直接爆拆矩阵的乘法运算，所以适用性肯定没有矩阵好，比如区间覆盖就比较难处理。
我们稍微结合一下两个方法的优点，考虑矩阵哪里是不动的，我们就只对剩下的位置进行计算，这样适用性会很高，常数也会变小。
那么现在，最基础的历史和线段树就讲完了。实现可能需要注意一下细节。
习题稍后更新。（我还没写/ll）

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...