动态RMQ问题解决办法与算法分析

发表于 | 分类于 | | 阅读次数:

在之前的一篇博文中，我们介绍了使用Sparse Table（ST稀疏表）解决RMQ问题的方法。使用ST稀疏表对已知数据进行预处理，对于任意的询问请求都可以以O(1)的效率进行解答，作为一种离线算法，非常高效快速，特别适合用于进行RMQ问题的求解。
现在让我们考虑一种动态的RMQ问题，动态是指在我们询问的过程中，区间内某一位置的值会受到外界干预而发生改变，我们需要做的就是在每次改变的基础上对收到的询问给出正确的结果。
对于动态RMQ问题我们有如下三种思路：

  • 使用朴素算法进行遍历查找；
  • 使用SparseTable稀疏表进行求解，每次变化更新稀疏表；
  • 使用二分线段树进行求解，每次变化进行相应的信息修改。
    下面我们在一个较小数据量(10^4)的条件下对上述三种算法进行分析实现。

题目描述

【输入】
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，意义如前文所述。
每组测试数据的第2行为N个整数，分别描述每种商品的重量，其中第i个整数表示标号为i的商品的重量weight_i。
每组测试数据的第3行为一个整数Q，表示小Hi总共询问的次数与商品的重量被更改的次数之和。
每组测试数据的第N+4~N+Q+3行，每行分别描述一次操作，每行的开头均为一个属于0或1的数字，分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行，如果该行描述一个询问，则接下来为两个整数Li, Ri，表示小Hi询问的一个区间[Li, Ri]；如果该行描述一次商品的重量的更改，则接下来为两个整数Pi，Wi，表示位置编号为Pi的商品的重量变更为Wi
对于100%的数据，满足N<=10^4，Q<=10^4, 1<=Li<=Ri<=N，1<=Pi<=N, 0<weight_i, Wi<=10^4。

【输出】
对于每组测试数据，对于每个询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。

【样例输入】

10
618 5122 1923 8934 2518 6024 5406 1020 8291 2647 
6
0 3 6
1 2 2009
0 2 2
0 2 10
1 1 5284
0 2 5

【样例输出】

1923
2009
1020
1923

朴素遍历解法

算法分析

朴素遍历算法也就是对于每个询问区间[l, r]，对区间中的数据进行遍历访问，最后求出其最小值即为所求。
其算法复杂度为：

预处理 查询 修改
O(1) O(N) O(1)
  • 预处理：因为是使用一个数组对数据进行存储，所以直接赋值建立数组即可，时间复杂度为O(1);
  • 查询：因为是在一个数组中进行特定下标数据的访问查找，所以时间复杂度为O(N)；
  • 修改：修改操作直接对特定数组下标元素进行赋值即可，所以时间复杂度为O(1)。

总体来说，使用朴素算法思路比较简单，构建也比较容易，只有查询的时候时间复杂度比较高，但对于10^4的数据量还是能够满足的。

最终代码

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
#include <iostream>
#define N 10010
using namespace std;
int main()
{
    int n, m;
    int oper, res, a, b;
    int node[N];
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> node[i];
    }

    cin >> m;
    while(m--)
    {
        cin >> oper >> a >> b;
        if(oper == 1)
        {
            node[a] = b;
        }
        else
        {
            res = node[a];
            for(int i = a; i <= b; ++i)
            {
                if(node[i] < res)
                    res = node[i];
            }
            cout << res << endl;
        }
    }
    return 0;
}

SparseTable稀疏表解法

算法分析

稀疏表算法实质就是一种动态规划的思想，由于数据是动态的，所以每次变化都要修改相应的状态表，其时间复杂度为：

预处理 查询 修改
O(NlogN） O(1) O(N)
  • 预处理：预处理就是生成稀疏表，分别以1、2、4、8 … 2^j为区间进行最小值比较计算，状态转移公式为：$$dp[i][j+1] = min(dp[i][j], dp[i + 2^j][j])$$即用相邻两个2^(j-1)的数据更新2^j，其时间复杂度为O(NlogN);
  • 查询：使用稀疏表可以以O(1)的时间复杂度进行询问的解答；
  • 修改：假设这个位置是a, 那么
    Len=1时，有1个dp包含a: dp[a, 1]
    Len=2时，有2个dp包含a: dp[a, 2] dp[a-1, 2]
    Len=4时，有4个dp包含a: dp[a, 4] dp[a-1, 4] dp[a-2, 4] dp[a-3, 4] …..
    直到Len=K(最接近N的2的整数幂)时, 有K个dp包含a: dp[a, k] dp[a-1, k] dp[a-2, k] … dp[a-k+1, k]
    所以总共就有1+2+4+…+K <= 2N个区间
    即修改的时间复杂度为O(N)

使用SparseTable算法虽然查询的时候能够达到O(1)的时间复杂度，但是因为动态数据进行修改的时间复杂度为O(N)，所以其时间复杂度也比较高。

最终代码

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
#include <iostream>
#include <algorithm>
#define N 10010
using namespace std;

int main()
{
    int n, m;
    int res, oper, a, b, k;
    int weight[N][15];

    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> weight[i][0];
    }

    k = log2(n);

    for(int j = 1; j <= k; ++j)
    {
        for(int i = 1; i + (1<<j) - 1 <= n; ++i)
        {
            weight[i][j] = min(weight[i][j-1], weight[i + (1<<(j-1))][j-1]);
        }
    }

    cin >> m;
    while(m--)
    {
        cin >> oper >> a >> b;
        if(oper == 0)
        {
            k = log2(b - a + 1);
            cout << min(weight[a][k], weight[b - (1<<k) + 1][k]) << endl;
        }
        else
        {
            weight[a][0] = b;

            for(int j = 1; j <= log2(n); ++j)
            {
                for(int i = a; a - i < (1<<j) && i > 0; --i)
                {
                    if(i + (1<<j) - 1 <= n)
                        weight[i][j] = min(b, weight[i][j]);
                    else
                        continue;
                }
            }
        }
    }
    return 0;
}

线段树解法

算法分析

线段树(Segment Tree)是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每个非叶子结点[a, b]，它的左子树代表的区间为[a,(a+b)/2]，右子树表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树。叶节点数目为N，即整个线段区间的长度。
使用线段树算法的时间复杂度为：

预处理 查询 修改
O(N） O(logN) O(logN)
  • 预处理：预处理即建树过程，使用DFS深度优先遍历构建树结构的时候每个结点都需要访问一次，更新每个结点的最小值的时候同样使用DFS对每个结点进行遍历，即每个结点访问两次执行操作，时间复杂度为O(N)；
  • 查询：对于查询，最复杂的情况就是一直遍历到树的底部也就是叶子结点，即查询区间内某一端点遍历到叶子结点，除此结点外的区间均在此前获得结果，所以查询的时间复杂度就是树的高度，也就是O(logN);
  • 修改：修改需要从树的底部，即从该叶子结点开始，更新修改其所有的祖先结点，即树的每一层修改一次，时间复杂度就是树的高度，即为O(logN)。

相对于朴素解法和SparseTable稀疏表解法修改和查询操作都有一个操作的时间复杂度为O(N)，我们使用线段树的方法得到了一个查询和修改时间复杂度均为O(logN)的算法，实现了两种操作时间复杂度的平衡。

最终代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//二分线段树
#include <iostream>
#include <map>
#define N 10010
using namespace std;

typedef struct node
{
    int left, right, value;
    node *father, *lchild, *rchild;
    node()
    {
        left = right = value = 0;
        father = lchild = rchild = NULL;
    }
    node(int left_, int right_) : left(left_), right(right_)
    {
        value = 0;
        father = NULL;
        lchild = NULL;
        rchild = NULL;
    }
}*Node;

int n, m;
int weight[N];
map<int, Node> findNode;
Node root;

void build(Node p)
{
    if(p->left == p->right)
        return;
    int mid = (p->left + p->right) / 2;
    p->lchild = new node(p->left, mid);
    p->lchild->father = p;
    p->rchild = new node(mid+1, p->right);
    p->rchild->father = p;
    build(p->lchild);
    build(p->rchild);
}

void dfs(Node p)
{
    if(p->left == p->right)
    {
        p->value = weight[p->left];
        findNode[p->left] = p;
        return;
    }
    dfs(p->lchild);
    dfs(p->rchild);
    p->value = min(p->lchild->value, p->rchild->value);
}

void modify(Node p)
{
    p->value = min(p->lchild->value, p->rchild->value);
    if(p->father)
        modify(p->father);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> weight[i];

    root = new node(1, n);
    build(root);
    dfs(root);


    int a, b, oper;
    cin >> m;
    while(m--)
    {
        cin >> oper >> a >> b;
        if(oper == 0)
        {
            cout << query(root, a, b) << endl;
        }
        else
        {
            weight[a] = b;
            findNode[a]->value = b;
            modify(findNode[a]->father);
        }
    }
    return 0;
}

二分线段树在更大数据量下的使用

正如我们上面所说的，我们使用线段树的方法得到了一个查询和修改时间复杂度均为O(logN)的算法，实现了两种操作时间复杂度的平衡。
由于上面题目要求的是10^4较小的数据量，所以三种方法都可以满足要求，但是如果我们将上述题目的数据量提高到10^6，数据量扩大了100倍，此时只有使用二分线段树才能够在规定时间内完成运算，其他两种方法均会超时。

最终代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//二分线段树
#include <iostream>
#include <map>
#define N 1000010
using namespace std;

typedef struct node
{
    int left, right, value;
    node *father, *lchild, *rchild;
    node()
    {
        left = right = value = 0;
        father = lchild = rchild = NULL;
    }
    node(int left_, int right_) : left(left_), right(right_)
    {
        value = 0;
        father = NULL;
        lchild = NULL;
        rchild = NULL;
    }
}*Node;

int n, m;
int weight[N];
Node findNode[N];
Node root;

void build(Node p)
{
    if(p->left == p->right)
        return;
    int mid = (p->left + p->right) / 2;
    p->lchild = new node(p->left, mid);
    p->lchild->father = p;
    p->rchild = new node(mid+1, p->right);
    p->rchild->father = p;
    build(p->lchild);
    build(p->rchild);
}

void dfs(Node p)
{
    if(p->left == p->right)
    {
        p->value = weight[p->left];
        findNode[p->left] = p;
        return;
    }
    dfs(p->lchild);
    dfs(p->rchild);
    p->value = min(p->lchild->value, p->rchild->value);
}

int query(Node p, int l, int r)
{
    if(l <= p->left && r >= p->right)
        return p->value;
    int mid = (p->left + p->right) / 2;

    if(r <= mid)
        return query(p->lchild, l, r);
    else if(mid < l)
        return query(p->rchild, l, r);
    else
        return min(query(p->lchild, l, mid), query(p->rchild, mid+1, r));
}

void modify(Node p)
{
    p->value = min(p->lchild->value, p->rchild->value);
    if(p->father)
        modify(p->father);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &weight[i]);

    root = new node(1, n);
    build(root);
    dfs(root);

    int a, b, oper;
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d%d%d", &oper, &a, &b);
        if(oper == 0)
        {
            printf("%d\n", query(root, a, b));
        }
        else
        {
            weight[a] = b;
            findNode[a]->value = b;
            modify(findNode[a]->father);
        }
    }
    return 0;
}
  • 注：这里为了提高算法效率将之前使用的cin和cout分别替换成scanf和printf。

平衡之于算法

方法 预处理 查询 修改
朴素算法 O(1) O(N) O(1)
ST稀疏表 O(NlogN） O(1) O(N)
线段树 O(N） O(logN) O(logN)
  • 平衡：无论是我们平时接触比较多的二叉平衡树，还是我们这次使用的二分线段树，都是通过一种平衡的方式实现了算法操作的优化升级；
  • 对于算法，我们讲究时间复杂度和空间复杂度，而且我们有各种时间换取空间和空间换取时间的例子，最普遍的动态规划就是一种空间换取时间的方法，两者之间也存在一种相互转换的平衡；
  • 针对上面的RMQ例题，如果我们99.9%的操作是进行修改，其余0.1%的操作是进行查询，则使用朴素算法最为适合，他的修改操作时间复杂度为O(1)；反之如果是99.9%的查询和0.1%的修改，则使用SparseTable稀疏表算法更为合适，查询操作时间复杂度为O(1)；然而对于比例相当或者不确定的请求就应该使用二分线段树这种平衡两种操作时间复杂度的算法了，这就是一种平衡、一种中庸的做法。

正所谓平衡之于算法之道！

-------------本文结束感谢您的阅读-------------
0%