RMQ（区间最值问题）

Range Maxinum/Mininum Query（又称ST表）可以通过dp+倍增预处理的方式从而达到 $O(n \log n)$ 的构建预处理，$O(1)$ 的查询。

初始化

我们可以通过先定义一个二维数组 $f_{i, j}$表示从第 $i$个数开始的区间大小为 $j$ 的最值。而由于一个区间的最值 $f_{i, j}$ 可以通过这个区间的两部分 $f_{i, j - 1} 和 f_{i + 2 ^ {j - 1}, j - 1}$得到，从而可以得到状态转移方程：

$$f_{i, j} = \max/\min(f_{i, j - 1}, f_{i + 2 ^{j - 1}, j - 1})$$

数组的第一维范围为数据的最大范围 $n$，第二维为数据最大范围的 $\log_{2} n$。因此构造的时间复杂度为 $O(n \log n)$。代码如下

1
2
3
4
5
6

void init()
{
    for (int j = 1; j < M; j++)
        for (int i = 1; i + (1 << j) -  1 <= n; i++)
            f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

区间查询

如果查询的区间为 $[l, r]$，那么令 $k$ 为所求的 $\log$ 数值，即 $k = \lfloor \log_{2} (r - l + 1) \rfloor$，从而 $2 ^ {k + 1} \geq r - l + 1$。

故可得答案 $ans$ 为：

$$ans = \min / \max (s_{l, k}, s_{r - 2^{k} + 1, k})$$

1
2
3
4
5
6

int query(int l, int r)
{
    int len = r - l + 1;
    int k = log2(len);
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}