ST表

Skyzhou666 · 2022-11-18 20:16:59 · 算法·理论

ST表（离线RMQ）

这篇讲得很好

与线段树比较

优点：预处理O(nlogn)，查询O(1)！线段树预处理相同，但查询还要O(logn)（码量比线段树少太多了！！

缺点也很明显：只能维护静态可重复贡献的数据的区间

PS：可重复贡献指的是对于运算opt，满足x\ opt\ x = x，比如最大值、最小值、最大公因数、最小公倍数、按位与、按位或等等

基于倍增思想

板子题 P3865

#include <iostream>
#include <cstdio>
#define MAXN 100001
using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n, m, f[MAXN][32], lg2[MAXN];

void Init()
{
    for(int x = 2; x <= n; x++) lg2[x] = lg2[x>>1] + 1;
    for(int x = 1; x <= lg2[n]; x++)
        for(int y = 1; y + (1<<x) - 1 <= n; y++)
            f[y][x] = max(f[y][x-1], f[y+(1<<(x-1))][x-1]);
}

int Query(int l, int r)
{
    int k = lg2[r - l + 1];
    return max(f[l][k], f[r-(1<<k)+1][k]);
}

int main()
{
    n = read(); m = read();
    for(int x = 1; x <= n; x++) f[x][0] = read();
    Init();
    while(m--)
    {
        int l, r;
        l = read(); r = read();
        printf("%d\n", Query(l, r));
    }
    return 0;
}

卡快读，卡log2，卡printf（printf比cout真的快了不是一点半点