随机说话
stripe_python · · 闲话
元素与范围
定义 元素是数据结构维护的最小单元。
举例:序列中的某个位置,树上某个节点,平面上某个格点。
定义 范围是元素全集的某个子集。
通常可以用少量信息表示大量元素。举例:序列上的区间,树的链 / 子树,平面上的矩形 / 半平面。
OI 中,常常将元素映射为
取
举例:
- 1-side 矩形:序列前缀
- 2-side 矩形:序列的区间,树的子树(拍 DFS 序),树的链(拍 HLD)
- 3-side 矩形:树的有向邻域(到子树根
\le k 的点)
将时间轴作为一个维度,动态问题可以升
维护手法
- 前缀和:前缀半群信息,区间群信息。
- ST 表:区间可重复贡献半群信息。
- 树状数组:单点修改,区间群信息。
- 线段树:单点修改,区间半群信息。
- 若修改是半群信息,且修改—信息满足双半群模型,则可以打懒标记做区间修改。
- 树剖线段树:单点 / 树链修改,树链半群信息。
- 使用毛毛虫剖分可以支持
1- 邻域范围修改查询。
- 使用毛毛虫剖分可以支持
- 树套树:单点修改,正交范围半群信息。
- KDT:正交范围修改,正交范围半群信息。
- 静态点分树:树上
k- 邻域群信息。
自由度理论
定义 将询问的参数个数,定义为问题的自由度。
举例:区间的自由度为
动态问题静态化需要升高
对于群信息,可以用差分的方法降低正交范围的自由度。
对一维扫描线可以降掉
分治可以降掉
莫队是广义扫描线。区间莫队降
函数式数据结构可以降