ST算法学习笔记

二月 15, 2019 5245

O(1) 查询区间最值

算法简介

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

——百度百科

ST（Sparse Table，稀疏表）算法是求解RMQ问题的经典在线算法，以O(nlogn)时间预处理，然后在O(1)时间内回答每个查询。

算法流程

ST算法实际上采用了DP的思想

初始化

定义 F(i,j) 表示区间 [i, i + 2^j - 1] 内的最小值， P[i] 为原序列

那么显然
MATHJAX-SSR-1691

状态转移方程？

首先，任意一个区间的最小值等于 min( 这个区间前一半的最小值 , 这个区间后一半点最小值 )
这个很好理解吧
把 F(\ ) 结合进去，就是

F(i,j) = min(F(i,j-1),F(i + 2^{j-1}, j - 1))

还有什么细节？
上面的式子看的你很想递归是吧（反正我是）
如果你不想递归的话，你八成会：

1
2
3
for (int i = 1; ...)
    for (int j = 1; ...)
        F[i][j] = ...

其实……这样都是错的，这样会导致有几个状态被过早地枚举

我们要把枚举 j 的循环放在外层，至于为什么……你模拟一下就行了

查询

此处的内容可能有点难以理解，请消化不了的同学多看几遍

上面说了查询是 O(1) 的听起来就好简单啊

实现确实是很简单，但是原理就……也是很简单

首先给你一个定理：
对于任意 x \in \mathbb{N^*} ，都有 2^{\lfloor log_2(x) \rfloor} > \lfloor \frac{x}{2} \rfloor

然后令查询区间 [l,r] 的长度 \text{len} = r - (l - 1),\ \text{ll} = log_2(\text{len})
那么根据上边可得 2^{\text{ll}} > \lfloor \frac{len}{2} \rfloor
这意味着什么？
这意味着查询的区间有重叠！
不过这并不能意味啥，重叠又怎么样，只是查询的区间变了

1
2
3
4
5
6
7
8
9
10
11
原来我们查询区间，都是查询这个区间的一半
比如更新[l,r]之间的最小值就是
f[l][r] = std::min(f[l][mid], f[mid + 1][r]);

但是这次不一样，这次的mid超过了区间的一半
那就可以这么写：

int Query(int l, int r) {
    int k = std::log(r - (l - 1)) / std::log(2);
    return std::min(f[l][k], f[r - ((1 << k) -1)][k]);
}

是 O(1) 的吧

它查询的区间相当于是这样的：
（画的不准确，仅供参考）

1
2
3
4
5
_ _ _ _ _ _ _ _ _ 
-------====       f[l][k]
       ====------ f[r - ((1 << k) - 1)][k]
       
等号就是两个查询区间的并集

这也就是它为什么不能查询区间和的原因
前缀和足够了

qwq

伪代码

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
\text{Algorithm 1: Sparse Table}
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
\text{Init(The Sparse Table } f, \text{The original sequence } a, \text{no return value})
   1. \text{For } i \text{ from 1 to n do}
   2. \ \ \ \ f[i][0] = a[i]
   3. \text{End For}
   4. \ j \leftarrow 1, i \leftarrow 1
   5. \text{While } 2^j \leq n \text{ do}
   6. \ \ \ \ \text{While } i + 2^j - 1 \leq n \text{ do}
   7. \ \ \ \ \ \ \ \ f[i][j] = min(f[i][j-1], f[i + 2^{j-1}][j-1])
   8. \ \ \ \ \ \ \ \ i \leftarrow i + 1
   9. \ \ \ \ \text{End While}
10. \ \ \ \ j \leftarrow j + 1
11. \text{End While}

\text{Query(}l,r\text{,return a value x})
1. k \leftarrow log_2(r - l + 1)
2. \text{return } x = min(f[l][k], f[r - (2^k - 1)][k]
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = (100000 + 10) * 2;
const int MAXLOG = 17 + 10; // floor(log2(100000 + 10))

int n, q;
int Table[MAXN][MAXLOG];

void BuildTable() {
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            Table[i][j] = std::max(Table[i][j-1], Table[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int Query(int l, int r) {
    int k = std::log(r - (l - 1)) / std::log(2);
    return std::max(Table[l][k], Table[r - ((1 << k) - 1)][k]);
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &Table[i][0]);
    // 这里可以省去seq[i]，对Table[i][0]进行直接写入
    BuildTable();
    for (int i = 1; i <= q; ++i) {
        int l = 0, r = 0;
        scanf("%d %d", &l, &r);
        printf("%d\n", Query(l, r));
    }
    return 0;
}

例题

洛谷P3865【模板】ST表