数据结构 (二): RMQ / 区间最值查询

小灰灰 2022-02-04 11:13 218阅读 0赞

### RMQ ###

*  简介
 *  RMQ 的组织方式
 *  代码 ( C语言 )
 *  总结

# 简介 #

在[上一篇博客中][Link 1]介绍的 BIT 数据结构用来进行单点修改和查询区间和, 而本篇的数据结构 RMQ (Range Minimum Query) 则用来进行区间最值查询.

# RMQ 的组织方式 #

RMQ 和普通数组的区别是: RMQ 是二维数组, 维度为  \{ N , l o g N \} \\\{N, logN\\\} \{ N,logN\}, 其中  r m q \[ i \] \[ j \] rmq\[i\]\[j\] rmq\[i\]\[j\] 表示的是从  a \[ i \] a\[i\] a\[i\] 开始长度为  2 j 2^j 2j 的区间的最小值, 那么显然, 它的初始化可以递归进行, 且复杂度为  O ( N l o g N ) O(NlogN) O(NlogN)  
当要查询  \[ L , R \] \[L, R\] \[L,R\] 区间的最小值时, 我们可以进行如下操作:

1.  记 len = R-L+1
2.  得到小与等于 len 的最大的 2 的幂次, 记为 k
3.  返回  m i n \{ r m q \[ L \] \[ k \] , r m q \[ R − 2 k \] \[ k \] \} min\\\{rmq\[L\]\[k\], rmq\[R-2^k\]\[k\]\\\} min\{ rmq\[L\]\[k\],rmq\[R−2k\]\[k\]\}

然后上述操作的复杂度为  O ( 1 ) O(1) O(1)

# 代码 ( C语言 ) #

#define MAXN 100000
    
    int rmq[MAXN][20];
    int min(int a, int b) { return (a<b)?a:b;}
    void init() { 
    	// rmq[:][0] is already inited
    	for (int step = 1; 1<<step < MAXN; step++) { 
    		for (int i = 0; i+(1<<step) < MAXN; i++) { 
    			rmq[i][step] = min(rmq[i][step-1], rmq[i+(1<<(step-1))][step-1]);
    		}
    	}
    }
    
    int rangeMin(int from, int to) { 
    	int len = to - from + 1;
    	int k = 0;
    	while ((1<<(k+1))<=len) k++;
    	return min(rmq[from][k], rmq[to-(1<<k)+1][k]);
    }

# 总结 #

这种二分的思想值得学习.!  
学!

[Link 1]: https://blog.csdn.net/vinceee__/article/details/89893578