526互联

ST表

发布时间 2023-11-30 17:18:57作者: blind5883

有点时间补一下这玩意吧

首先先说明RMQ是一类问题, 指 区间最大最小值, 而ST表是解解决RMQ问题的一把手术刀
(手术刀, 锋利但不通用)

作用

O(logn)的预处理
O(1)的区间最大值查询
不可以更改区间数值

原理

原理是倍增

我们将设f[i][j]是从i处向外2^j格里面的最大值

因为任何区间长度len, 无论怎么分, 其最多只需要两个f[i][j]就可以完全覆盖它

len, 可以分成比他小的最大的2^n, 那么len - 2^n < 2^n, 如果不符合这个的话, n 就可以
继续往上加, 知道符合这个等式, 而且不能等于, 如果等于那么len = 2^n +2^n = 2^(n + 1),
n依旧可以往上加, 因此我们知道我们只需要两个f[i][j]就可以完全覆盖len这个区间)

实现

问题来了怎么实现它

预处理

也很简单, 根据之前倍增lca的思想, 即f[i][j] = f[f[i][j - 1]][j - 1], 即我们把一步
拆成两步走, 有了递推式, 那么求出它就很简单了

而求出ST表, 也就是预处理就是下面代码

for (int j = 0; j < M; j ++ ) // M是logn上取整, 即包含整个n
	for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
		if (j == 0) f[i][j] = w[i]; // 如果只跳一步, 那么最大值就是这个值它本身
		else f[i][j] = max(f[i][j], f[f[i][j - 1]][j - 1]); // 注意是求最大值

这个时间复杂度很好判断, 最坏O(nlogn)
但是是很小的logn, 能从循环中看出来(手术刀)
因为有预处理, 所以是不能更改原数组的, 否则必须再次预处理(但这样就不如用线段树了)

查询

怎么查询呢？
你要知道, 最大值是可以累加贡献的, 如[1, 5]的最大值, 等于[1, 3]的最大值和[2, 5]的
最大值的最大值, 虽然2和3重复使用了, 但是答案是正确的, 即可以累加贡献

我们已经得到了f数组, 根据上面的性质, 那么就很简单了,
我们设lg[i]为logi下取整
那么从i到j之间的长度是len = j - i + 1
最大值就是, max(f[i][lg[len]], f[j - (1 << lg[i]) + 1][lg[len]]), 这句话你细品

j - (1 << lg[i]) + 1说一下, 这是代表这个区间开头, 比如[2, 5]里面有4个数, 你从5减4
得1, 但是你的区间是从2开始的, 所以要加上1, 由区间长度计算公式 j - i + 1 = len,
也可以得到i = j - len + 1这个式子

lg数组

上面提到了lg数组, lg[i]为logi下取整

为什么使用这个数组而不是, 直接log2(n)呢?

这里是为了保证查询的O(1), 如果调用log2()函数的话, 时间复杂度会增加, 而通过预处理
lg数组的方式, 就可以保证查询O(1)

lg数组一般预处理一遍即可, 是n的时间复杂度, 可以直接加在上面的预处理里面,

代码

int last = 0;
for (int i = 1; i <= n; i ++ )
{
	while (1 << last <= i) last ++ ;
	lg[i] = last - 1;
}

例题

ST表(跳表)

/* 
    中心思想: 倍增
    设f[i][j]是从i处向外2^j格里面的最大值;
    
    预处理是O(nlogn)
    查询是O(1)的
    
    无法修改
    只能查询
    像树状数组一样的"手术刀"
    
    因为查询耗时O(1), 所以在"特殊情况"下没法被O(log)的线段树替代
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = log2(N) + 1;

int n, m;
int w[N];
int f[N][M];
int lg[N];

void init()
{
    for (int j = 0; j < M; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (j == 0) f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

    int last = 0;
    for (int i = 1; i < N; i ++ ) // log数组, 这里的预处理是自己写的, 利用一个last能干好多事
    {
        while (1 << last <= i) last ++ ;
        lg[i] = last - 1;
    }
}

int query(int l, int r)
{
    int len = r - l + 1;
    return max(f[l][lg[len]], f[r - (1 << lg[len]) + 1][lg[len]]);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    init();
    cin >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << endl;
    }
    
    return 0;
}

线段树

/*
    线段树的话, 比较简单就不打注释了
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 200010;

int w[N];
int n, m;

struct Node
{
    int l, r;
    int maxv;
}tr[N * 4];

void pushup(int u)
{
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, l, w[l]};
    else
    {
        int mid = l + r >> 1;
        tr[u] = {l, r, -0x3f3f3f3f};
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int maxv = -0x3f3f3f3f;
        if (l <= mid) maxv = query(u << 1, l, r);
        if (r > mid) maxv = max(maxv, query(u << 1 | 1, l, r));
        
        return maxv;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);
    scanf("%d", &m);
    
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}