使用线段树预处理。能够使得查询RMQ时间效率在O(lgn)。

线段树是记录某范围内的最小值。

标准的线段树应用。

Geeks上仅仅有两道线段树的题目了。并且没有讲到pushUp和pushDown操作。仅仅是线段树的入门了。

參考：http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

我改动了一下他的程序，使用pushUp操作。事实上也是非常easy的一个小函数。并且手动计算了下，认为他的动态分配内存，计算须要的树的大小，这样做好像也省不了多少内存。

只是方法不错。能够学习下。

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <limits.h>

inline int LC(int rt) { return rt<<1; }

inline int RC(int rt) { return rt<<1|1; }

inline int minV(int x, int y) { return x < y ? x : y; }

inline void pushUp(int *segTree, int rt)

{

	segTree[rt] = minV(segTree[LC(rt)], segTree[RC(rt)]);

}

int RMQUtil(int *segTree, int qs, int qe, int l, int r, int rt)

{

	if (qs <= l && r <= qe)

		return segTree[rt];

	int res = INT_MAX;

	int m = l + ((r-l)>>1);	//写错没提示：l + ((r-l)>1)

	if (qs <= m) res = RMQUtil(segTree, qs, qe, l, m, LC(rt));

	if (m < qe) res = minV(RMQUtil(segTree, qs, qe, m+1, r, RC(rt)), res);

	return res;

}

int RMQ(int *segTree, int n, int qs, int qe)

{

	// Check for erroneous input values

	if (qs < 1 || qe > n || qs > qe)

	{

		puts("Invalid Input");

		return -1;

	}

	return RMQUtil(segTree, qs, qe, 1, n, 1);

}

void constructSTUtil(int arr[], int l, int r, int *segTree, int rt)

{

	if (l == r)

	{

		segTree[rt] = arr[l];

		return ;

	}

	int m = l + ((r-l)>>1);

	constructSTUtil(arr, l, m, segTree, LC(rt));

	constructSTUtil(arr, m+1, r, segTree, RC(rt));

	pushUp(segTree, rt);

}

int *constructST(int arr[], int n)

{

	int h = (int)(ceil(log((double)n)/log((double)2))) + 1;

	int treeSize = (1 << h);//1024须要开2048数组。 比一般开3倍或者4被数组省不了太多内存，由于1025就须要开4倍了，一般开3被能够。开4倍就肯定不会超内存了

	int *segTree = (int *) malloc(treeSize * sizeof(int));

	constructSTUtil(arr, 1, n, segTree, 1); //从1開始构建

	return segTree;

}

int main()

{

	int arr[] = {0, 1, 3, 2, 7, 9, 11};//0位置不使用

	int n = sizeof(arr)/sizeof(arr[0]);

	// Build segment tree from given array

	int *st = constructST(arr, n);

	int qs = 2;  // Starting from 1

	int qe = 6;  

	// Print minimum value in arr[qs..qe]

	printf("Minimum of values in range [%d, %d] is = %d\n",

		qs, qe, RMQ(st, n, qs, qe));

	free(st);

	return 0;

}