如果这篇博客帮助到你,可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 (除特别声明或转载文章外)
网上没搜到欧拉序做法的博客,所以我就写了这篇博客。
利用欧拉序将 LA(Level-Ancestors) 问题转化为 $\pm 1$ FS(Find-Smaller)问题
注意到,$x$ 的深度为 $d$ 的祖先,在欧拉序上,是 $x$ 后面的第一个深度 $\le d$ 的节点,问题转化为 FS 问题,并且欧拉序具有 $\pm 1$ 性质,所以问题变为 $\pm 1$ FS 问题,该问题有着线性预处理,常数查询的在线做法。
$i$ 后面第一个 $\le x$ 的数的位置,记作 $\mathrm{FS}(i,x)$。
$\pm 1$ FS 问题的 $\mathrm O(n\log n)$ 预处理,$\mathrm O(1)$ 查询的在线做法
定义 $\mathrm {ctz}(i)$ 表示最大的满足 $2^k\mid i$ 的 $k$。
定义 $\mathrm{lbt}(i,j)$($i\le j$)表示,$[i,j]$ 内的所有整数中 $\mathrm{ctz}$ 最大的数;当 $i\le 0$ 时,定义其值为 $0$。
引理 对于任意 $i,j$($i\le j$),令 $k=\mathrm{lbt}(i,j)$,显然有 $i-j+1\le 2^{\mathrm{ctz}(k)+1}$,以及 $i-k+1\le 2^{\mathrm{ctz}(k)}$。
$\pm 1$ FS 问题中给出的数组为 $a_{0\sim n-1}$,定义 $f(i)=3\times2^{\mathrm{ctz}(i)}$,$f(0)=n$。
对于每个 $0\le i<n$,预处理出数组 $B_{i,1\sim f(i)}$,其中 $B_{i,j}=\mathrm{FS}(i,a_i-j)$。
查询 $\mathrm{FS}(i,x)$ 时:
- 若 $x\ge a_i$,答案为 $i$;
- 令 $d=a_i-x$,若 $d\le f(i)$,答案为 $B_{i,d}$;
- 否则,令 $k=\mathrm{lbt}(i-d+1,i)$,答案为 $B_{k,a_k-x}$。
接下来给出证明。
首先证明 $a_k-x\le f(k)$: \(\begin{aligned} 2^{\mathrm{ctz}(k)+1}&>i-(i-d+1)=d-1=a_i-x-1\\ 2^{\mathrm{ctz}(k)}&>i-k\\ 3\times2^{\mathrm{ctz}(k)}&\ge a_i+i-k-x\ge a_k-x \end{aligned}\) 注意 $a_i+i-k\ge a_k$ 来自于 $\pm 1$ 性质。
然后证明 $\mathrm{FS}(k,x)=\mathrm{FS}(i,x)$。
有 $k>i-d=i-a_i+x$,即,$a_k\cdots a_i$ 所有数都 $\ge a_i-(i-k)>x$,所以有 $\mathrm{FS}(k,x)=\mathrm{FS}(i,x)$。
注意这一证明也依赖于 $\pm 1$ 性质。
$B$ 数组的预处理是简单的,显然有 $B$ 数组的总长是 $\mathrm O(n\log n)$ 的。
由此,我们获得了 $\mathrm O(n\log n)$ 预处理,$\mathrm O(1)$ 查询的在线做法。
$\mathrm O(n)$ 预处理,$O(1)$ 查询
首先按 $\mathrm O(\log n)$ 分块。
块间
第 $i$ 个块表示编号为 $ib\sim ib+b-1$ 的点。
对每个块,存储 $N_{i,1\sim 2b}$,其中 $N_{i,j}=\mathrm {FS}(ib,a_{ib}-j)$。
对每个块,存储 $F_{i,1\sim f(i)}$,其中 $F_{i,j}=\left\lfloor\frac{\mathrm{FS}(ib,a_{ib}-jb)}{b}\right\rfloor$,即 $\mathrm{FS}(ib,a_{ib}-jb)$ 所在的块。
注意到有令 $k=F_{i,j}$,则有 $a_{ib}-jb\le a_{kb}<a_{ib}-(j-1)b$,这一式子可以简单的使用 $\pm 1$ 性质给出证明。
查询 $\mathrm{FS}(ib+j,x)$($j<b$)时:
- 若 $x\ge a_{ib+j}$,返回 $ib+j$;
- 若 $j>0$:
- 通过块内查询,若答案在块内,则直接返回;
- 若答案不在块内,返回 $\mathrm{FS}((i+1)b,x)$;
- $j=0$:
- 若 $x\ge a_{ib}-2b$,返回 $N_{i,a_{ib}-x}$;(3)
- 令 $d=\left\lfloor\frac{a_{ib}-x}{b}\right\rfloor$:
- 若 $d\le f(i)$,令 $k=F_{i,d}$,返回 $\mathrm{FS}(kb,x)$;(2)
- 否则,令 $k=\mathrm{lbt}(i-d+1,i)$,返回 $\mathrm{FS}(kb,x)$。(1)
通过与之前证明类似的方式,我们可以证明,情况(1)一定会跳转至情况(2),这里不多赘述。
接下来证明情况(2)一定会跳转至情况(3)。 \(a_{kb}<a_{ib}-(d-1)b<x+2b\) 由此,我们获得了块间的处理方式。
块内
接下来介绍的是利用位掩码的方法,这种方法块长一般取 $w$。 \(m(i,j)=\begin{cases}1&a_j<\min\{a_i,\dots,a_{j-1}\}\\0&\mathrm{otherwise}.\end{cases}\) 那么,$m(ib+j,ib+j+1),m(ib+j,ib+j+2)\dots m(ib+j,ib+(b-1))$ 中第 $a_{ib+j}-x$ 个 $1$ 的位置就对应 $\mathrm{FS}(ib+j,x)$,如果不存在这样的位置,则说明答案不在块内。
我们将 $m(ib+j,ib+j+1),m(ib+j,ib+j+2)\dots m(ib+j,ib+(b-1))$ 压入一个数 $m_{ib+j}$ 内,查询即为查找第 $k$ 个为 $1$ 的二进制位位置,这一操作可以进行一些预处理后 $O(1)$ 实现。(据说存在部分硬件支持相关指令直接查询,我不太了解这方面)
由此,我们获得了块内的处理方式。
至此,我们获得了解决 LA 问题的线性预处理,常数在线查询的算法。
原论文最后给了点申必常数优化,我是完全没看懂,贴个链接。