让线段树求 RMQ 成为时代的眼泪！

众所周知，树状数组的优势在于可以方便地维护可差分的信息，并且常数极小无比。

但是，碰到 RMQ 等不可差分维护的信息，$\text{OI}$ 中主流的做法就只有上线段树（动态）或者 ST 表（静态）了（不排除也有丧心病狂的四毛子）。

但是，我们可以树状数组！！！

考虑一种暴力的想法：从 $r$ 开始往前跳。设当前位置为 $p$。

如果 $p-\text{lowbit}(p) \ge l$，则用 $\text{tree}_p$ 更新 $ans$，并 $p\leftarrow p-\text{lowbit}(p)$。
否则，用 $a_p$ 更新 $ans$，并 $p\leftarrow p-1$。

Theorem: 这样做的复杂度是单次询问 $O(\log^2 n)$ 的。

证明：

考虑：如果 $p$ 与 $l$ 不同的最高一位是 $p$ 的最低位，下一次跳跃一定会把 $p$ 的这一位变成 $0$，使得不同的最高位右移至少一位。

又因为如果 $p$ 与 $l$ 不同的最高一位不是 $p$ 的最低位，下一次跳跃一定会跳第一种，使得最低位左移至少一位。

所以：经过 $\log n$ 次跳跃后，$p$ 与 $l$ 不同的最高一位一定会右移至少一位。

所以：跳跃次数为 $O(\log ^2 n)$。$\square$

复杂度：

预处理 $O(n)/O(n\log n)$（取决于实现），单次询问 $O(\log^2{n})$，空间 $O(n)$，但是常数较小。

~~好吧还不如线段树~~

请先对 BIT 的形态有一定了解！

注意到上一个方法的问题在于区间不能被完整表示时，我们只能一次跳一格，这样效率十分低下：

考虑 ST 表是怎么做的：

我们可以找到两个区间，各自都能被完整表示出来，拼在一起（可以有重复），就是要求的区间！

我们把这个思想搬到 BIT 上！

考虑维护一正一反两棵 BIT（第一棵就是普通的树状数组，第二棵又被称作后缀 BIT。

查询 $[l,r]$ 的时候，我们先从正 BIT 的 $l$ 节点开始往上跳父亲，直到节点编号 $>r$。我们将经过的 $\le r$ 的点编号拿出来，记作 $a$。

接着，我们从反 BIT 的 $r$ 节点开始往上跳父亲，直到节点编号 $<l$。我们将经过的 $\ge l$ 的点编号拿出来，记作 $b$。

Lemma: $a$ 的最后一个元素一定等于 $b$ 的最后一个元素。

证明：

设 $l,r$ 的二进制表示的 $\text{lcp}$ 长度为 $f$，则 $l$ 二进制下的第 $f+1$ 位一定为 $0$，$r$ 的第 $f+1$ 位一定为 $1$。

$\therefore$ 在若干次跳父亲操作后，$l,r$ 二进制下的前 $f$ 位一定不变，第 $f+1$ 位一定为 $1$，从第 $f+2$ 位开始一定都为 $0$。

容易发现，这一定是最终状态。$\square$

因此，我们得到了原序列一个区间的「fenwick 拆分」：

$$\blue{[l, l+\text{lowbit}(l)-1],[l+\text{lowbit(l)}, ...], ...},[p,p],\red{...,[r-\text{lowbit}(r)+1, r]}$$

其中 $p$ 为 $a$ 中最后一个元素，即两次跳父亲的相遇点。

容易发现，蓝色部分的最值在反 BIT 中都有维护，红色部分的最值在正 BIT 中都有维护，中间的 $p$ 直接查原序列即可。

复杂度分析：

预处理 $O(n)/O(n \log n)$，单次询问 $O(\log n)$，空间复杂度 $O(n)$，常数极小。

可以看到，已经和一份正常实现的 ST 表差不多快了。