推导方程#

我们令 $st[i][j]$ 表示原序列中第 $i$ 个数字起（含）往后 $2^j$ 个，也就是原数组 $a[i]$ 到 $a[i+2^j-1]$ （两边都含）的区间最大值。显然，对于单个的 $a[i]$ 的区间的最大值就是 $a[i]$ 本身。而这一段区间的长度为 $1=2^0$ 。所以我们可以得到 $st[i][0]=a[i]$ 。

然后我们继续初始化st表。我们要先定下来区间长度 $2^j$ ，再枚举第 $i$ 个数（为什么要这样的顺序呢？请往下看）。现在我们想要得出 $st[i][j]$ ，也就是 $a[i]$ 到 $a[i+2^j-1]$ 的区间最大值，应该由哪些 $st$ 转移过来呢？答案是 $st[i][j-1]$ 和 $st[i+(1<<(j-1))][j-1]$ 。为什么呢？

对于一个区间，如果它的长度为 $2=2^1$ ，那么它就由两个长度为 $1$ 的区间得来（因为区间为 $1$ 的 $st$ 早就处理好了）。长度为 $4=2^2$ ，是由两个长度为 $2$ 的区间得来的。以此类推，我们发现只要把当前区间对半分，就能推导出当前区间的值了。原因很简单，我们的st表的第二位是 $2^j$ ，这也决定了它是由一个一个的 $2$ 累积起来的结果。

我们已经知道了上一个区间的长度是 $2^{j-1}$ ，也就是 $st$ 数组的第二维是 $j-1$ 。下面我们来推导第一维是几。例如，对于 $[1, 4]$ 这个区间，两个子区间是 $[1, 2]$ 和 $[3, 4]$ 。可以知道较大的那个区间的左端点是 $3$ ，这是大区间的左端点加上区间长度的一半得到的，也就是 $i+2^{j-1}$ 。由于st表只需要知道左端点和区间长度即可，那么两个 $st$ 分别是 $st[i][j-1]$ 和 $st[i+(1<<(j-1))][j-1]$ 。

注意，$1<<k=1^k$ ，这应该不难理解。下面是对于每个 $st$ 转移的代码：

1
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

现在也解答了两层循环遍历顺序的问题。假使我们一定要先枚举第一维 $i$ ，对于每一个 $a[i]$ 计算它在某个区间内的贡献。然而这个区间是往后的，也就是说， $a[i]$ 以后的 $st$ 全没有处理好，也就无法递推了。

循环条件#

1. 第一层循环：枚举 $j$ ，范围： $2 \leq len = 2^j \leq n$ ，即 $1 \leq j \leq log_2{n}$ （由于 $st[i][0]$ ，就是长度为 $1$ 的情况已经得知了，不用再来一遍）。
2. 第二层循环：枚举 $i$ ，即考虑当前 $a[i]$ 对于 $j$ 所规定的区间的贡献。由于长度为 $2^j$ ，所以 $1 \leq i$ 且 $i+[1<<(j-1)] \leq n$ 。刚才不是说长度为 $2^j$ 吗？那为什么不是 $i+(1<<j)$ 呢？因为st表要把 $a$ 中末尾几个数字也要考虑进去。那么我们只需满足推导方程中数组中的条件 $st[i+(1<<(j-1))][j-1]$ 即可。

以上理解似乎有些问题，有待改进。

区间查询#

现在已经完成了预处理，要来进行查询了。给定区间 $[l, r]$ ，要求其中的最大值。如果这个 $[l, r]$ 恰好是 $st$ 中已有的区间，那最好了，直接输出。若 $[l, r]$ 的长度恰好不是 $2^j$ 的整区间呢？那就要把这个区间再分成两块。可是，即使是这样也不能保证这两个被分出来的区间的长度是 $2^j$ 。既然我们不能恰好分，那就让这两个区间有所重叠吧。于是我们得到了查询函数：

1
int solve(int l,int r){
2
    return max(st[l][(int)log2(r-l+1)],st[r-(1<<int(log2(r-l+1)))+1][(int)log2(r-l+1)]);
3
}

这里应该不难理解。下面给出完整代码。