网上没搜到欧拉序做法的博客，所以我就写了这篇博客。

利用欧拉序将 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 问题的线性预处理，常数在线查询的算法。

原论文最后给了点申必常数优化，我是完全没看懂，贴个链接。