当前位置: 首页 > news >正文

历史和线段树

我们一般在处理区间修改的操作时,会在线段树上打懒标记,意思是这个结点所代表的区间中的所有数都要同时进行一系列修改。为了更容易理解历史和线段树,我们先来回顾一下普通线段树的区间加操作。

\(\mathbf{Preperation}\)

引理

对于区间加,区间求和问题,我们在做线段树时,有结论:子节点的懒标记时间比父节点的懒标记靠前。


我们把注意力放在父子结点的懒标记之间的时间关系上,我们发现,操作后,新的被打上标记的顶点 \(t\),它的父亲节点的标记都被下放了,所以父亲结点的懒坐标只可能在之后出现。

\(\mathbf{Part. 1}\)

进入正题。

给你一个序列 \(a_1\)\(a_n\),初始全为 \(0\)。你需要支持如下操作:

  • \([l, r]\) 区间中的每个数 \(a_i\) 加上 \(y\)
  • 查询 \([l, r]\) 在历史每个时刻的和的总和

容易想到每次修改的时候,我们对 \([l, r]\)\(a_i\) 区间加。然后,我们在全局上打一个历史和更新的标记。

我们对每个结点,记录三个信息,分别是 \(his, sum, len\),表示这个区间的历史和,区间和,区间长度。由引理,我们知道在下放懒标记和单点加标记的时候,可以视作一些懒标记在前,一些懒标记在后,现在要合并在一起。

但这没有只有加法标记的时候那么显然,因为现在还有一个历史和更新操作,不是很好合并。

下文介绍两种方法。(还有一种我觉得不涉及历史和线段树的思想,不在赘述)

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

我们考虑刻画这两种标记分别在对这三个信息做什么。

  • 区间加标记 \(v\)\(sum = sum + len \times v\)
  • 历史和更新标记:\(his = his + sum\)

实际上,这两种标记都只是在这三个变量里做线性变换,因此考虑用矩阵刻画。

我们把要存储的信息全部列在矩阵里,也就是 \(\begin{bmatrix}his\\sum\\len\end{bmatrix}\),那么有:

  • 区间加标记 \(v\):乘上 \(\begin{bmatrix}1 & 0 & 0 \\0 & 1 & v\\0 & 0 & 1\end{bmatrix}\)
  • 历史和更新标记:乘上 \(\begin{bmatrix}1 & 1 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}\)

现在,标记的合并都被刻画成了矩阵乘法,于是就十分好做了。

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

我们直接考虑如何合并两个标记队列。假设有两个标记队列 \(A, B\)\(A\) 在前,\(B\) 在后。我们先把只在 \(A\) 或者 \(B\) 内的贡献加起来,计这个内部贡献为 \(ret\)。那么,我们只需要计算两个标记队列之间的贡献即可。

对于 \(A\) 队列里的任意一个加法标记,它在 \(B\) 每次历史和更新时都会被算一次,因此两边之间的贡献就是 \(add_A \times upd_B\),其中 \(add_A\) 表示 \(A\) 中的加法标记和,\(upd_B\) 表示 \(B\) 中的历史和更新标记个数。

我们对每个结点,再计三个数 \(add, upd, ret\) ,用来表示整个标记队列。那么我们考虑一次下放操作,有 \(sum = sum + add'\)\(ret = ret + ret' + add \times upd'\)\(add = add + add'\)\(upd = upd + upd'\)。根据这个转移即可。


我们比较一下这两种方法。

  • 矩阵计 tag 适用性十分高,因为只需要你的操作都是线性变换,就可以用矩阵做。但缺点是常数比较大。
  • 暴力考虑标记序列合并,其实相当于直接爆拆矩阵的乘法运算,所以适用性肯定没有矩阵好,比如区间覆盖就比较难处理。

我们稍微结合一下两个方法的优点,考虑矩阵哪里是不动的,我们就只对剩下的位置进行计算,这样适用性会很高,常数也会变小。

那么现在,最基础的历史和线段树就讲完了。实现可能需要注意一下细节。

习题稍后更新。(我还没写/ll)

http://www.hskmm.com/?act=detail&tid=34553

相关文章:

  • 大数据分析之MySQL学习2
  • [KaibaMath]1012 关于收敛数列保号性的推论的证明
  • 申公豹说
  • 赛前训练 12 树的直径、中心和重心
  • 关于无人巡航小车的学习笔记
  • 详细介绍:springboot+vue智慧旅游管理小程序(源码+文档+调试+基础修改+答疑)
  • 存算一体架构的先行者:RustFS在异构计算环境下的探索与实践
  • 2-SAT
  • CSP-S模拟10
  • CSP-S模拟赛加赛 比赛总结
  • 我要好好写博客了 - Milo
  • 洛谷P4735--最大异或和
  • DAPO代码实现浅析
  • [KaibaMath]1011 关于收敛数列保号性的证明
  • Appium 3.0:跨平台移动自动化测试框架全面解析
  • 赛前训练 12 extra 树上差分倍增
  • 塔吊施工人员操作合规性监测!思通数科 AI 卫士实时守护作业安全
  • Dos命令1
  • 题解:P1073 [NOIP 2009 提高组] 最优贸易
  • 吩咐
  • 互评五
  • 机器人技术新前沿:自动驾驶路径规划算法解析
  • 前端框架文档新思路:基于源码解析的自动化方案
  • 常用模板
  • C++ std::forwardT 的使用
  • tryhackme-预安全-网络基础知识-数据包和帧-07
  • 迈向零信任存储:基于RustFS构建内生安全的数据架构
  • 如果这就是人类脑海的话 雪白纸上划出血红层层痕迹 不如杀死这些记忆
  • 嗣澳——扫,墨依奥——描,希伊桉——线
  • 服务器被攻击!原因竟然是他?真没想到...