ST表

ST table

1.思想

一般用于解决RMQ (Range Minimum/Maximum Query)问题。

倍增的思想1—>2—>4—>8—>16

我们先处理出所有区间长度为1的最小值

表示左端点为，区间长度为的区间的最小值。即：


那么：

对于一段区间,

我们要找的最大的(因为最大的一定能使得我们找的这两个区间把整个区间覆盖。)

这样我们一定能找到两个长度为的区间，分别是和（这两个区间有交集是没有关系的）

即:每次询问我们把它分成两部分，分别是和，其中,两部分结果取就是答案。

2.局限性

1. 易看出，只有当区间中重叠的部分对最终答案无影响时，才能使用 st 表。

​ 比如区间&，|，gcd是可以的，但像求区间*或者区间+就是不行的了

2. 不能进行修改操作

3. 复杂度：建表，查询

4. eg.RMQ

给个数,个询问。

每个询问给定两个数，求出中的最大值。

//读入
 unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%d%u%u%u", &n, &q, &A, &B, &C);
    for (int i = 1; i <= n; i++) {
        a[i] = rng61();
    }
    for (int i = 1; i <= q; i++) {
        unsigned int l = rng61() % n + 1, r = rng61() % n + 1;
        if (l > r) swap(l, r);
    }
}  

代码：

//O(nlogn)建表，O(1)查询
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1010000;
int n,q,lg[N];
unsigned int A,B,C,a[N],ans;
//unsigned int f[N][22];
unsigned int f[22][N];//尽量让靠里的那一维连续的变，让内存访问更加连续


inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}

int main(){
    scanf("%d%d%u%u%u", &n, &q, &A, &B, &C);
    for (int i = 1; i <= n; i++) {
        a[i] = rng61();
        f[0][i] = a[i];
    }
    // for(int j = 1;j<=20;j++)
    //     for(int i = 1;i+(1<<j)-1<=n;i++)
    //         f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
      for(int j = 1;j<=20;j++)
        for(int i = 1;i+(1<<j)-1<=n;i++)
            f[j][i] = max(f[j-1][i],f[j-1][i+(1<<(j-1))]);

    lg[1] = 0;//2^0
    for(int i = 2;i<=n;i++)//手写,对2求lg取下整
        lg[i] = lg[i/2]+1;

    for (int i = 1; i <= q; i++) {
        unsigned int l = rng61() % n + 1, r = rng61() % n + 1;
        if (l > r) swap(l, r);
        //写法1
        //int len = lg[r-l+1];
        //写法2
        //int len = __lg(r-l+1);
        //写法3
        int len = 31-__builtin_clz(r-l+1);//__builtin_clz数二进制位的前导0
        //2^x<=len,2^(x+1)>len   
        ans ^= max(f[len][l],f[len][r-(1<<len)+1]);
    }
    cout<<ans<<endl;
}  


5.ST 表维护其他信息

除了RQM之外，还有其它的「可重复贡献问题」，例如「区间按位和」、「区间按位或」、「区间 GCD」，ST 表都能高效地解决。

6.板子代码

struct S_T {
    // op 函数需要支持两个可以重叠的区间进行合并
    // 例如 min、 max、 gcd、 lcm 等
    ll f[22][N], lg[N];
    void build(int n) {
        lg[0] = -1;

        for (int i = 1; i <= n; ++i) {
            f[0][i] = a[i];
            lg[i] = lg[i / 2] + 1;
        }

        for (int i = 1; i <= 20; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                f[i][j] = __gcd(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    }
    void clear(int n)
    {
         for (int i = 1; i <= 20; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                f[i][j] = 0;
    }
    ll query(int l, int r) {
        if(l <= n && r > n)return __gcd(query(l,n),query(1,r-n));
        int len = lg[r - l + 1];
        return __gcd(f[len][l], f[len][r - (1 << len) + 1]);
    }
} ST;