静态区间半群信息并学习笔记（附复杂度下界证明）

· · 算法·理论

前言

文章大概翻译了 Noga Alon 和 Baruch Schieber 的论文。

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

如果满足 a\times b=b\times a，即有交换律，那么这个半群就称为交换半群。矩阵乘法是半群，但它不是交换半群，因为矩阵乘法没有交换律。

如果信息可减，即存在逆元，那么这就是一个群，可以用前缀和 \mathcal O(n)-\mathcal O(1)。

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

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

假设一次查询可以使用 k 个半群信息，即进行 k-1 次半群运算，那么预处理的时间复杂度和空间复杂度可以做到 \mathcal O(n\lambda (k,n))（把 k 视为常数，k\ge 2)。

如果要求在线性的时间复杂度和空间复杂度内预处理，那么查询可以做到 \mathcal O(\alpha(n))。

同时，上述提到的时间复杂度可以证明是下界。

核心思想是分块套分块，递归到子问题。

一些约定

需要维护的信息是半群信息，可能不是交换半群信息。

假设只能对半群信息使用半群中的运算，即不能采用基数排序之类的，也不能使用压位。

这里的复杂度指的是运算次数，即假设一次半群运算可以在 \mathcal O(1) 的时间复杂度内进行。

半群信息并用乘法 \times 或 \prod 表示。

一些符号

A(i,j)= \begin{cases} 2j&,i=0\\ 1&,i>0\land j=0\\ A(i-1,A(i,j-1))&,i>0\land j>0 \end{cases} B(i,j)= \begin{cases} j^2&,i=0\\ 2&,i>0\land j=0\\ B(i-1,B(i,j-1))&,i>0\land j>0 \end{cases} 例如 $\lambda (0,n)=\lceil\frac n 2\rceil$，$\lambda (1,n)=\lceil\sqrt n\rceil$，$\lambda(2,n)=\log n$，$\lambda (3,n)=\log \log n$，$\lambda (4,n)=\log ^*n$。 此外，还有 $\lambda (k,n)=\min\{i|\lambda^{(i)}(k-2,n)\le 1\}$，其中 $\lambda ^{(1)}(k,n)=\lambda(k,n),\lambda ^{(i)}(k,n)=\lambda(i,\lambda^{(i-1)}(k,n))$。 最后有阿克曼函数 $\alpha(n)$ 为最小的 $i$ 使得 $A(i,i)\ge n$。 ## 区间半群信息并 ### 上界 需要构造一个算法使得可以取到上文提到的复杂度。 对于 $k=1$，只能使用一个半群信息，因此必须要预处理出每一个区间的半群信息并，时空复杂度均为 $\mathcal O(n^2)$。注意虽然 $\lambda (1,n)=\lceil\sqrt n\rceil$，但时空复杂度显然不能做到 $\mathcal O(n\sqrt n)$。 对于 $k=2$，只能二区间合并，直接用猫树维护即可做到 $\mathcal O(n\log n)$ 预处理，这是经典的。 对于 $k>2$ 考虑分块。每 $B=\lambda (k-2,n)$ 分一块，分了 $m=\frac{n}{B}$，块内维护前缀积以及后缀积。对于一次查询，如果左右端点都在同一个块内，那么递归到子问题，即每个块内。此时依然可以使用 $k$ 个半群信息，因此块内是一个子问题。如果左右端点不在同一个块内，那么需要调用一个前缀积以及一个后缀积，只剩下 $k-2$ 个半群信息余额，因此块间需要用 $k-2$ 的子问题维护。 举一些例子。$k=3$ 的时候使用 Sqrt Tree，每 $B=\sqrt n$ 个分一块，块内维护前缀积后缀积，$\sqrt n$ 个块之间对维护每一对 $[l,r]$ 维护第 $l$ 个块到第 $r$ 个块的积，即块间用 $k=1$ 的结构维护；块内继续使用 Sqrt Tree 维护。每次查询需要一个后缀积、一个整块的积、一个前缀积，三个半群信息。由于每次开根 $\log n$ 会除以二，所以预处理的时空复杂度为 $\mathcal O(n\log\log n)$，而 $\lambda(3,n)=\log \log n$。$k=4$ 的时候使用 Extend Sqrt Tree，每 $B=\sqrt n$ 个分一块，块内维护前缀积后缀积，块间用猫树维护，即 $k=2$ 的结构；块内继续用 Extend Sqrt Tree 维护。每次查询需要一个后缀积、猫树中的二区间合并、一个前缀积，四个半群信息。由于每次会使得 $n$ 变成 $\log n$，所以预处理的时空复杂度为 $\mathcal O(n\log^* n)$。其中 $\log^*$ 为迭代对数函数。 分析时间复杂度，时间复杂度应为 $\mathcal O(kn\lambda (k,n))$，由于 $k$ 是常数因此可以看成 $\mathcal O(n\lambda(k,n))$。归纳证明，$T_k(n)\le \frac{n}{\lambda(k-2,n)}T_k(\lambda(k-2,n))+kn$。后面的 $+kn$ 是，由 $k$ 的问题递归到 $k-2$ 的子问题，再递归到 $k-4$ 的子问题以此类推，由于每次除的 $\lambda (k-2,n)$ 很小可以忽略，递归 $\mathcal O(k)$ 层，因此得到这个系数。 当只能线性预处理的时候，构造一个算法使得可以 $\mathcal O(\alpha(n))$ 查询。 一个简单的算法是建线段树，可以 $\mathcal O(n)$ 预处理 $2\lceil\log n\rceil= \mathcal O(\log n)$ 查询。考虑每 $B=2\alpha^2(n)$ 分一块，询问落到块内查询的复杂度为 $\mathcal O(\log \alpha(n))<\mathcal O(\alpha(n))$，是正确的。块间用 $k=2\alpha(n)$ 的结构维护。那么一次查询需要 $2\alpha(n)+2=\mathcal O(\alpha(n))$ 次半群信息并，而预处理的时间复杂度为 $\mathcal O(\alpha(n)\cdot \frac{n}{\alpha^2(n)}\cdot \alpha(n))=\mathcal O(n)$。注意到这里 $\alpha(n)$ 不再被视为常数，因此计算复杂度时要考虑到。 这样，一次查询如果可以使用 $k$ 个半群信息，那么预处理的时间复杂度和空间复杂度可以做到 $\mathcal O(n\lambda (k,n))$；如果要求 $\mathcal O(n)$ 预处理，查询的时间复杂度可以做到 $\mathcal O(\alpha(n))$。 ### 下界 尝试证明 $\Omega(n\lambda(k,n))$ 为一次查询可以使用 $k$ 个半群信息时的复杂度下界。 定义 $P$ 为 $[1,n]=\{i|i\in[1,n]\cap \Z\}$ 的一些子集构成的集合，对于 $Q\in P$，已经预处理出了 $\prod _{i\in Q}a_i$ 的结果。称 $P$ 是 $k$ 覆盖的，当且仅当对于 $[1,n]$ 的每一个子区间 $[l,r]=\{i|i\in[l,r]\cap \Z\}$，都可以表示成 $P$ 中不超过 $k$ 个元素（这里的元素是 $[1,n]$ 的子集）的并，表示一次查询至多使用 $k$ 个半群信息。 要证明 $\Omega(n\lambda(k,n))$ 为复杂度下界，只需要证明 $P_k(n)\ge \Omega(n\lambda(k,n))$，而实际的问题要比这个情形严格，因为： 1. 由于 $Q$ 是子集而不是子区间，强行进行乘法需要保证这个群是交换半群。 2. 由于只要求并为 $[l,r]$，不要求选出的若干个区间没有交，这意味着这个群是幂等半群。 3. 并不能保证每一个 $Q\in P$ 都可以进行 $\mathcal O(1)$ 次乘法从其它 $Q'$ 推出。 因此这个下界的证明对交换半群、幂等半群均成立。 归纳法证明，先证明 $k=2$ 的情况，再证明 $k>2$ 的情况。 对于 $k=2$，需要证明 $P_2(n)\ge \Omega(n\log n)$。即需要证明 $P_2(n)\ge 2P_2(\frac n 2)+\Omega (n)$。 对于区间 $[1,n]$，令 $m=\lceil \frac n 2\rceil$。把区间分成 $[1,m-1],[m,m],[m+1,n]$ 三个部分，称为 $I_1,m,I_2$。对于 $I_1,I_2$ 的子区间，$P_2(n)$ 中需要分别包含可以组成它们的集合，这部分需要 $2P_2(\frac n 2)$ 个集合。对于额外的 $\Omega(n)$ 个集合，它们需要包含 $I_1$ 中的元素、$m$、$I_2$ 中的元素，至少两种类型的元素。这里有两种情况： 1. 如果对于每个 $x\in [1,m-1]$，一个 $k$ 覆盖的 $P$ 中均存在一个最小值为 $x$、且包含 $[m,n]$ 中元素的一个集合。那么此时，至少需要包含额外的 $m-1=\Omega(n)$ 个集合。 2. 如果存在一个 $x\in[1,m-1]$，一个 $k$ 覆盖的 $P$ 中所有最小值为 $x$ 的集合均不包含 $[m,n]$ 中的元素。对于 $y\in[m,n]$，考虑查询 $[x,y]$，这时为了凑出 $x$，需要使用一个 $I_1$ 的最小值为 $x$ 的子集。注意到区间 $[m,y]$ 还没有进入并集，那么就需要一个包含 $m$ 且以 $y$ 为最大值的集合。这样的集合一定时“额外的集合”，且有 $n-m=\Omega(n)$ 个。 综上，对于 $k=2$，可以证明 $P_2(n)\ge \Omega(n\log n)$。 对于 $k>2$，考虑归纳证明。需要证明 $P_k(n)\ge \frac{n}{B}P_k(B-1)+\Omega(n)$。 把区间 $[1,n]$ 每 $B=\lambda(k-2,n)$ 分一块，分出 $m=\frac{n}{B}$ 块，形如 $jB$ 的位置不属于任何一个块，记第 $j$ 块的子区间为 $I_j$。对于第 $j$ 块，需要 $P_k(B-1)$ 个集合才能表示出它的所有子区间。接下来只需要证明还需要 $\Omega(n)$ 个额外的子区间。 定义 $k$ 覆盖的 $P$ 的元素 $Q$ 是“全局的”当且仅当 $Q$ 不是任何一块的子集。定义一个位置 $x$ 是“全局的”当且仅当存在一个全局的 $Q$ 使得 $x$ 为 $Q$ 中的最大值或最小值。定义一个子区间 $[l,r]$ 是“全局的”当且仅当 $[l,r]$ 中所有位置都是全局的。这里有两种情况： 1. 有至少 $\lfloor \frac m 2\rfloor$ 个全局的子区间（这里的子区间指的是 $I_j$，即块），每个全局子区间至少包含 $B-1$ 个全局的位置。由于一个全局子区间只会最多产生两个全局的位置，因此总共需要 $\frac m 4 (B-1)=\Omega(n)$ 个全局的子集。 2. 其它的情况，也就是说至少有 $\lfloor \frac m 2\rfloor$ 个不是全局的子区间（这里的子区间也指的是块）。令 $x\in I_{j_1},y\in I_{j_2}$ 为非全局位置，那么凑出区间 $[x,y]$，至少需要一个 $I_{j_1}$ 中一个以 $x$ 为最小值的子集、$I_{j_2}$ 中一个以 $y$ 为最小值的子集、和凑出 $I_{j_1+1},I_{j_1+2},\dots,I_{j_2-1}$ 的子集。由于前面用了 $2$ 个子集，剩下只剩 $k-2$ 个子集，因此把不是全局的块拿出来，就是一个 $\frac m 2$ 的 $k-2$ 的子问题，至少需要包含 $\Omega(\frac m 2\lambda(k-2,\frac m 2))=\Omega(n)$ 个额外的子集。 综上，对于 $k>2$，可以证明 $P_k(n)\ge \Omega(n\lambda(k,n))$。