RMQ之线段树解法

缘起

RMQ问题（Range Minimum/Maximum Query）指的是对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题. 本文给出线段树解法.

分析

线段树解法是显然的——需要使用点线段树. 首先使用数组进行建树. 然后回答询问. 这是一种在线（online）算法. 算法的复杂度是 O(N)~O(logN). 前面一个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
#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#define LOCAL

using namespace std;

const int MAX_N = 20; // 最多20个数

int a[MAX_N] = {0x3f3f3f3f,2,1,3,4,8,5,-1,19,-4,27,89,2,7}; // 索引0不用于存储数据

struct
{
	int begin,end;
	int _min, _max; // 该节点代表在 [begin,end]的区间上最大值是 _max 最小值是 _min 
} segmenttree[MAX_N<<2];

inline int getmid(int i){return (segmenttree[i].begin+segmenttree[i].end)>>1;}

bool build(int begin, int end, int i) // 使用 a[begin,...,end]建树, 当前节点是segmenttree[i]
{
	segmenttree[i].begin = begin;
	segmenttree[i].end = end;
	if (begin==end) return segmenttree[i]._max = segmenttree[i]._min = a[begin];
	int mid = (begin+end)>>1;
	build(begin, mid, i<<1);
	build(mid+1, end, i<<1|1);
	segmenttree[i]._max = max(segmenttree[i<<1]._max, segmenttree[i<<1|1]._max);
	segmenttree[i]._min = min(segmenttree[i<<1]._min, segmenttree[i<<1|1]._min);
	return true;
}

void rmq(int begin, int end, int i, int &_max, int &_min) // 获取 a[beign, end]的极值(结果保存在_min和_max中), segmenttree[i]是当前节点
{
	if (begin==end)
	{
		_max = _min = a[begin];
		return;
	}
	if (begin==segmenttree[i].begin && end==segmenttree[i].end)
	{
		_max = segmenttree[i]._max;
		_min = segmenttree[i]._min;
		return;
	}
	int mid = getmid(i);
	if (end<=mid)
	{
		rmq(begin, end, i<<1, _max, _min);
	}
	else if (begin>mid)
	{
		rmq(begin, end, i<<1|1, _max, _min);
	}
	else
	{
		int _max1, _max2, _min1, _min2;
		rmq(begin,mid,i<<1, _max1,_min1);
		rmq(mid+1,end,i<<1|1, _max2, _min2);
		_max = max(_max1, _max2);
		_min = min(_min1, _min2);
	}
}

int main()
{
	build(1,13, 1);
	int i,j, _max,_min;
	while(~scanf("%d%d", &i, &j))
	{
		rmq(i,j,1,_max,_min);
		printf("%d %d\n", _max, _min);
	}
	return 0;
}