《挑战程序设计竞赛》读书笔记(六)线段树和RMQ
本文是《挑战程序设计竞赛》中线段树一节的读书笔记。主要介绍了线段树和RMQ(range minimun query)的原理和实现。
线段树:
线段树适合于处理区间。如图组织管理区间。
节点可以存放不同的数据,在书中实现了RMQ(Range Minimum Query)操作的数据结构。
RMQ是指给定若干个数据a[],找出a[i…j]的最小值,同时允许更新a[k]。
针对RMQ,线段树的每个节点维护对应区间的最小值。如图所示。
那如何执行RMQ呢,我们以求a[0..6]的最小值为例说明。为方便,我们对所有节点进行编号,按行从0开始,如图。现在,考察a[0..6]的最小值。
首先,我们根据图能够知道,第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,如果需要更新最小值,就更新,否则保持不变停止(没必要继续向上更新了)。
关于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; } } |