记录
9:21 2024-3-10
ST算法其实就是利用倍增的思想去划分区间
利用ST算法求RMQ问题(区间最值问题)
\(F[i,j] 表示数列A在子区间[i, i + 2^j - 1]里数的最大值 F[i,0] = A[i]\)
\(F[i,j] = max(F[i, j - 1], F[i + 2^{j - 1}, j - 1])\)
求[l,r]最值的时候 求出满足 \(2^k < r - l + 1 <= 2^{k + 1}\)的k
那么[l,r]最值就是 \(max(F[l, k], F[r - 2^k + 1, k])\)
点击查看代码
// 区间最值问题的ST算法
void ST_prework() {
for (int i = 1; i <= n; i++) f[i][0] = a[i];
int t = log(n) / log(2) + 1;
for (int j = 1; j < t; 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]);
}
int ST_query(int l, int r) {
int k = log(r - l + 1) / log(2);
return max(f[l][k], f[r - (1<<k) + 1][k]);
}