RMQ

ACM

RMQ(range maximum/minimum query),可以用线段树或者ST实现

ST表

使用动态规划的思想，不断的更新区间的最值。
d[i][j]表示以i为起点，区间的长度为\(2_j\)的最值。
首先枚举区间的长度，然后枚举区间的起点，不断的更新d[][]的值。

当我们查询区间[l, r]的最值的时候，我们首先求出\(2^k\le r-l+1\)最大的k值，例如：[5, 11], 最大的k值为2， 那么min(5, 11) =min(min(5, 8), min(11-2^2+1, 11))

结合代码

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int d[maxn][21];
int number[maxn];
int n;
void init_rmq(){
    for(int i=1; i<=n; i++){
        d[i][0] = number[i];
    }
    for(int j=1; (1<<j)<=n; j++){//枚举长度
        for(int i=1; i+(1<<j)-1<=n; i++){//枚举起点
            d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);
        }
    }
}
int rmq_min(int l, int r){
    int len = floor(log2(r-l+1));
    return min(d[l][len], d[r-(1<<len)+1][len]);
}
int main()
{
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++){
            scanf("%d", &number[i]);
        }
        init_rmq();
        int q, l, r;
        scanf("%d", &q);
        for(int i=0; i<q; i++){
            scanf("%d%d", &l, &r);
            cout<<rmq_min(l, r)<<endl;
        }
    }
    return 0;
}

用rmq来求LCA

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int maxv = 1e6+10;
vector<int> G[maxv];
int root;
int vs[maxv*2+10];
int depth[maxv+10];
int id[maxv];
int d[maxv][21];
void dfs(int v, int p, int d, int &k){
    id[v] = k;
    vs[k] = v;
    depth[k++] = d;
    for(int i=0; i<G[v].size(); i++){
        if(G[v][i]!=p){
            dfs(G[v][i], v, d+1, k);
            vs[k] = v;
            depth[k++] = d;
        }
    }
}
void rmq_init(int* depth, int n){
    for(int i=0; i<n; i++){
        d[i][0] = depth[i];
    }
    for(int j=1; (1<<j)<=n; j++){
        for(int i=0; i+(1<<j)<=n; i++){
            d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);
        }
    }
}
int rmq_min(int u, int v){
    if(id[u]<id[v]){
        int len = floor(log2(id[v]-id[u]+1));
        int val = min(d[id[u]][len], d[id[v]-(1<<len)+1][len]);
        for(int i=id[u]; i<=id[v]; i++){
            if(depth[i] == val)
                return vs[i];
        }
    }
    else{
        int len = floor(log2(id[u]-id[v]+1));
        int val = min(d[id[v]][len], d[id[u]-(1<<len)+1][len]);
        for(int i=id[v]; i<=id[u]; i++){
            if(depth[i] == val)
                return vs[i];
        }
    }
}
int n, m;
int main(){
    scanf("%d", &n);
    for(int i=0; i<n-1; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int d = 0, k = 0;
    int root = 1;
    dfs(root, -1, d, k);
    rmq_init(depth, n*2);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            printf("%d -- %d: %d\n", i, j, rmq_min(i, j));
        }
    }
    return 0;
}

未解决的问题

本文标题:RMQ

文章作者:Babydragon

发布时间:2018-02-28, 10:15:35

最后更新:2018-03-23, 13:32:16

原始链接:http://baolintian.github.io/2018/02/28/RMQ/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. ST表
    1. 1.1. 代码
  2. 2. 用rmq来求LCA
  3. 3. 未解决的问题
{{ live2d() }}