ST表 学习笔记

发表于 | 分类于 | | + s

模板及讲解
运用st表实现区间询问区间最大/最小，初始化时间复杂度$O(nlogn)$, 查询$O(1)$
设$dp(i,j)$为从i开始长度为$2^j$的区间最小值，初始化合并结果即可，查询采用”两头补”方式
模板题：poj 3264

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;

const int MAXN = 50000 + 5;

int n, q;
int h[MAXN], fmaxi[MAXN][25], fmini[MAXN][25];
//h为原数组，fmaxi[i][j]为从i开始长度为2^j的区间最小值 

void initRMQ() {
    for (int i=1;i<=n;i++) fmaxi[i][0] = fmini[i][0] = h[i];//初始值为原数组 
    for (int j=1;(1<<j)<=n;j++) {//j必定在外层 
        for (int i=1;i+(1<<j)-1<=n;i++) {
            fmaxi[i][j] = max(fmaxi[i][j-1], fmaxi[i+(1<<(j-1))][j-1]);
            fmini[i][j] = min(fmini[i][j-1], fmini[i+(1<<(j-1))][j-1]);//DP
        }
    }
}
int RMQMax(int x, int y) {
    int k = (int)(log(y-x+1.0)/log(2.0));
    return max(fmaxi[x][k], fmaxi[y-(1<<k)+1][k]);
}
int RMQMin(int x, int y) {
    int k = (int)(log(y-x+1.0)/log(2.0));
    return min(fmini[x][k], fmini[y-(1<<k)+1][k]);
}
void clear() {}
void init() {
    clear();
    for (int i=1;i<=n;i++) scanf("%d", &h[i]);
    initRMQ();
}
void solve() {
    for (int i=1;i<=q;i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", RMQMax(a, b) - RMQMin(a, b));
    }
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n, &q)==2&&n&&q) init(), solve();
    return 0;
}

常见题型
1、求区间最大/最小值
Q：给出一个区间，询问某个子区间的最大/最小值。(没有修改操作)
解：因为不用修改，所以用RMQ$O(1)$查询最优，常数也小。
例题：poj 3264
2、求LCA
Q：给出一棵树，求两个节点的LCA。
解：
例题：

------ 本文结束 ------