ST 表

定义

范围最值查询（Range Minimum Query，RMQ）要求回答数组 \(A[1\ldots n]\) 上区间 \([l, r]\) 的最小值或最大值。ST 表是一种用于静态 RMQ 的预处理数据结构。

构造方法

思路

令 \(f[k][i]\) 表示从 \(A[i]\) 开始、长度为 \(2^k\) 的区间的最值。

\[ f[k][i] = \min\bigl(f[k-1][i], f[k-1][i + 2^{k-1}]\bigr). \]

查询区间 \([l, r]\) 时，令 \(k = \lfloor \log_2(r-l+1) \rfloor\)。两个长度为 \(2^k\) 的区间 \([l, l+2^k-1]\) 和 \([r-2^k+1, r]\) 能覆盖整个查询区间，因此最小值为

\[ \min\bigl(f[k][l], f[k][r-2^k+1]\bigr). \]

同理，将 \(\min\) 换成 \(\max\) 即可求区间最大值。

实现

void build() {
    for (int i = 1, j = 1, k = -1; i <= n; ++i) {
        if (i == j) {
            log2_floor[i] = ++k;
            j <<= 1;
        } else {
            log2_floor[i] = k;
        }
    }

    for (int i = 1; i <= n; ++i) st[0][i] = a[i];
    for (int k = 1; (1 << k) <= n; ++k) {
        for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
}

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