LoopJump's Blog

《挑战程序设计竞赛》读书笔记6-线段树和RMQ

2014-02-07

线段树：

线段树适合于处理区间。如图组织管理区间。

rmq.png

节点可以存放不同的数据，在书中实现了RMQ（Range Minimum Query）操作的数据结构。

RMQ是指给定若干个数据a[]，找出a[i…j]的最小值，同时允许更新a[k]。

针对RMQ，线段树的每个节点维护对应区间的最小值。如图所示。

min.png

那如何执行RMQ呢，我们以求a[0..6]的最小值为例说明。为方便，我们对所有节点进行编号，按行从0开始，如图。现在，考察a[0..6]的最小值。

get_range_min.png

首先，我们根据图能够知道，第0个节点存放了a[0..7]的最小值，所以，我们只能继续递归处理节点1和节点2。节点1表示了a[0..3]的最小值3，这个最小值对我们来说是有用的，并且我们也没必要继续考察节点3和节点4了。然后考察节点2，同节点0，我们再递归，如此继续，我们发现，为了求a[0..6]的最小值，我们只需比较图中橙黄色的三个数字就可以了。

所以，根据当前节点对应区间和所查询的区间的关系，分成如下三种情况。

  1.  如果当前节点对应区间和所查询的区间没有交集，那么说明这个区间不影响我们查找最小值，所以当前节点返回一个不影响结果的值。

  2.  如果所查询的区间包含了当前节点对应的区间，那么就返回当前节点的值作为候选最小值之一。

  3.  不是上述两种情况（如同本例中节点0的情况），需要递归求解。

这个算法的复杂度是多少呢？虽然看起来像是二叉树递归，但是，复杂度是O(n)，因为节点个数总共是2n个。

下面我们看如何更新一个值，即设置a[k]=value。我们以更新a[0]=2为例。

由于父子节点之间是包含关系，所以更新a[k]只需要从下往上，一直更新到根节点即可。

例如，更新a[0]=2，则为：

从节点7更新节点3，然后是节点1，最后是节点0，如果需要更新最小值，就更新，否则保持不变停止（没必要继续向上更新了）。

update.png

关于RMQ的实现代码，我写了一份，供大家参考。

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
#include <iostream>
using namespace std;

#define INT_MAX 999999

class RMQ {
public:
    RMQ(int size_) {
        size = size_;
        data = new int[ 2*size-1 ];
        for (int i = 0; i < 2*size-1; i++) {
            data[i] = INT_MAX;
        }
    };

    void update(int k, int value);
    int query(int a, int b);
    int hQuery(int a, int b, int k, int l, int r);

    void display(){
        for (int i = 0; i < 2*size-1; i++) {
            cout<< "data["<<i<<"] =  "<<data[i]<<endl;
        }
    };

    int size;
    int* data;
};

int min(int x, int y) {
    if ( x < y )
        return x;
    return y;
}

void RMQ::update(int k, int value) {

    k = k + size - 1;
    data[k] = value;

    while ( k > 0 ) {
        k = (k-1)/2;
        data[k] = min( data[2*k+1], data[2*k+2] );
    }
}

// get min in range [a,b)
int RMQ::query(int a, int b){
    return hQuery(a, b, 0, 0, size);
}

// get min in range [a,b)
// other parameter is used for convenient.
int RMQ::hQuery(int a, int b, int k, int l, int r){

    if ( r <= a || l >= b )
        return INT_MAX;

    if ( a <= l && b >= r)
        return data[k];

    int left_min = hQuery(a, b, 2*k+1, l, (l+r)/2);
    int right_min = hQuery(a, b, 2*k+2, (l+r)/2, r);
    return min(left_min, right_min);
}

int main(){

    RMQ rmq(8);

    rmq.update(0,5);
    rmq.update(1,3);
    rmq.update(2,7);
    rmq.update(3,9);
    rmq.update(4,6);
    rmq.update(5,4);
    rmq.update(6,1);
    rmq.update(7,2);

    rmq.display();

    int l, r, res;
    while(1){
        cin >> l;
        cin >> r;
        res = rmq.query(l, r);
        cout<< res <<endl;
    }
}
← 《挑战程序设计竞赛》读书笔记5-尺取法 Ubuntu 12.04编译安装3.15.6新内核 →

扫描二维码，分享此文章