lxl魔法学习笔记

这个算法可以处理一些修改比较奇怪的数据结构题，比如多边形修改、半平面修改、圆修改。

出处：《Offline Optimal Range Query and Update Algorithm》

可以叫 TB5 分治。

参考自 lxl 的 apio2022 课件《范围修改查询问题》以及 WC2024 营员交流的课件。

半群

给定集合 D 和 D 上的一个二元运算 *：D * D \to D。

满足结合律 a * (b * c) = (a * b) * c。

在半群的基础上还存在幺元 a * \epsilon = \epsilon * a = a。

在半群的基础上还满足交换律 a * b = b * a。

我们发现我们做的大多数数据结构题都是在维护半群信息，比如区间和、区间最大值、区间最大子段和。

并且我们在同时维护两个半群，即我们要查询的信息以及标记。

给定一个大小为 n 的点集 S 以及 m 次操作。

每个点维护的信息是半群 (D , +) 中的元素，修改是半群 (M , *) 中的元素，同时存在二元运算 \times：D \times M \to D。

简单来说，D 就是要查询的信息，M 就是要打的标记。

结合律：\forall a \in D , b , c \in M : a \times (b * c) = (a \times b) * c（对 a 进行 b , c 两次修改就等价于对 a 进行一次把 b , c 合并之后的修改）

分配律：\forall a , b \in D , c \in M : (a + b) \times c = a \times c + b \times c （对一个大的范围修改就等价于对两个小的范围分别修改）