随机说话

· · 闲话

元素与范围

定义 元素是数据结构维护的最小单元。

举例:序列中的某个位置,树上某个节点,平面上某个格点。

定义 范围是元素全集的某个子集。

通常可以用少量信息表示大量元素。举例:序列上的区间,树的链 / 子树,平面上的矩形 / 半平面。

OI 中,常常将元素映射为 B 维空间中的整点,范围变为 B 维正交范围。

取 B=2,就是所谓的 A-side 矩形。

举例:

将时间轴作为一个维度,动态问题可以升 1 维转化为静态问题。

维护手法

自由度理论

定义 将询问的参数个数,定义为问题的自由度。

举例:区间的自由度为 2,4-side 矩形的自由度为 4。

动态问题静态化需要升高 1 个自由度。

对于群信息,可以用差分的方法降低正交范围的自由度。

对一维扫描线可以降掉 1 个自由度。

分治可以降掉 1 个自由度,并且可以嵌套分治。举例:时间轴 CDQ 分治,二区间合并分治,树上点 / 边分治。

莫队是广义扫描线。区间莫队降 2 个自由度,所谓带修莫队降 3 个自由度,其中一个是时间轴带来的。

函数式数据结构可以降 1 个自由度。常见的应用是保存 1-side 范围的历史版本,询问时作差求解。举例:区间 / 树链 kth。