区间半群信息并在线查询学习笔记

· · 算法·理论

半群是一个二元运算的代数系统，其满足封闭性和结合律，如 (\min ,+) 卷积就是一个半群。

如果满足 a\times b=b\times a，即有交换律，那么这个半群就称为交换半群。

如果信息可减，即存在逆元，那么可以用前缀和 O(n)-O(1)。

如果满足 a\times a=a，即幂等半群信息，那么可以用 ST 表做到 O(n)-O(1)。

如果都不满足，那么可以用线段树做到 O(n)-O(\log n)。

猫树

对于线段树上的每一个节点，维护其对应区间的前缀和以及后缀和，那么查询只需要 1 次信息合并。这称为猫树。如果把序列补成 2 的幂次，那么通过位运算求最长公共前缀来做到 O(1) 定位区间。复杂度为 O(n\log n)-O(1)。

Sqrt Tree

考虑分块，以 \sqrt n 为块长。块内维护前缀和以及后缀和，块间维护整块的信息和（是 O(\sqrt n \times \sqrt n) 的），块内再使用下一层 Sqrt Tree 维护。每一层信息量都是 O(n) 的，进入下一层区间长会开根。复杂度为 O(n\log\log n)-O(1)。

Extend Sqrt Tree

考虑分块，以 \log n 为块长。块内维护前缀和以及后缀和，块间用猫树维护（是 O(n\log n\times \log n) 的），块内再使用下一层 Extend Sqrt Tree 维护。每一层信息量都是 O(n) 的，进入下一层区间长会 \log 一次。复杂度为 O(n\log ^* n)-O(1)。

Ackermann Tree

考虑分块。设 T(m,n) 表示用一个 m 级数据结构维护长度为 n 的序列后，数据结构的高度。以 T(m,n) 为块长，块内维护前缀和以及后缀和，块间用 m-1 级数据结构维护，块内用 m 级数据结构维护。每一层信息量都是 O(n)。

设 S(m,n) 表示一个 m 级数据结构，要使得高度至少为 n，所需要的序列长度至少是多少。容易得到 S(m,n)=S(m-1,S(m,n-1))。因为每一块的长度是 S(m,n-1)，而这个要求下一层数据结构的高度为 S(m,n-1)，所以所需的长度是 S(m,n)=S(m-1,S(m,n-1))。

发现这个就是阿克曼函数，所以数据结构的高度是反阿克曼函数，复杂度为 O(n\alpha (n))-O(\alpha(n))。