Content
#
ST(Sparse Table,稀疏表)算法采用了
倍增原理,在 O(nlogn)时间构造一个二维表之后,可以在 O(1)时间在线查询[l, r]区间的最值,有效解决在线
RMQ(Range Minimum/Maximum Query,区间最值查询)问题。
设 F[i, j]表示[i, i+2^j-1]区间的最值,区间长度为 2^j。
根据倍增思想,长度为 2^j 的区间可被分成两个长度为 2^(j-1) 的子区间,然后求两个子区间的最值即可。递推公式:
F[i, j]=max(F[i, j-1], F[i+2^(j-1), j-1])
ST创建
#
若数组长度为n,最大区间长度为 \(2^k \le n \le 2^(k+1)\),因此
\[k = \log_2 n\]
for (int i = 1; i <= n; i++) {
F[i][0] = a[i];
}
int k = log2(n);
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= n - (1 << j) + 1; i++) {
F[i][j] = max(F[i][j-1], F[i + 1 << (j - 1)][j - 1])
}
}
以下面数组为例,写出ST。
...