扫描模型
把偏序条件线性化,增量维护充分统计量,在切点读取查询;状态可以是覆盖重数、DP 表或单调前沿。标签 数学 / 扫描线 / Sweep line / 离线 / 偏序 / DP
定义
设 ,表示有限全序时间轴。
是集合,表示状态空间,初始状态 。
对每个 给定转移 。状态序列定义为
一个查询 由二元组 表示,其中 是切点, 是泛函。
查询 的答案为 。
记
称这样的数据为一个扫描模型。扫描线算法就是构造一个扫描模型,使 等于原问题的答案,并且 的更新与 的求值可由数据结构高效实现。
构造扫描模型
构造扫描模型通常需要定义一个基于状态空间 和全序轴 的事件模型
其中 是事件集, 是事件上的偏序, 把事件作用到状态上, 是 线性扩展。若 ,则扫描模型的转移为
事件 对扫描模型只暴露三项:它在 中的位置、转移 ,以及它是否属于查询的依赖集。
构造时需要确定:
- 事件集 与偏序 ;
- 状态空间 、初态 与转移 ;
- 线性扩展 ,从而得到 ;
- 查询 与依赖集 。
查询切点必须满足
即所有依赖事件都已在 之前处理。同一坐标可能有多个事件,需要用类型优先级或编号把它们排成线性扩展;这决定严格/非严格条件和读写顺序。
状态与充分性
设 是前 个事件构成的前缀。状态 是 的充分统计量:若两个前缀有相同的 ,则所有切点为 且 的查询答案相同。等价地,每个这样的查询答案都只依赖于 。
状态不限于几何截面;它是前缀的充分统计量,截面只是其特例。若把更新生成的变换幺半群记为 ,则 是 -集,扫描是前缀词的作用。 不必是群;、、并集等交换幺半群都适用,只有删除操作需要逆元。
常见误解
- 把扫描线等同于矩形并或计算几何:后者只是覆盖型状态的一个实例。
- 把状态等同于截面:状态是充分统计量,截面只是其特例。
- 认为状态必须成群:、、并集等交换幺半群即可;只有删除需要逆元。
- 认为同一时间步内的操作可交换:读写顺序是扫描模型的一部分;矩形周长并、Make Square 都依赖它。
- 认为扫描线必须在线:扫描线通常是离线线性化,需要预先知道事件与查询。
- 认为必须按坐标轴排序:任何线性扩展都可以;下标、时间、右端点都常用。