「Note」RMQ算法

RMQ

RMQ 即范围最小值问题 $(Range$ $Minimum$ $Query)$
支持==查询从$A_l, A_{l+1},A_{l+2}...，A_r$中的极值$(Max$ $or$ $Min)$==

算法思想

设$dp_{i,j}$为左端点为$i$， 右端点为$2^j(1 << j)$数组中的极值。

可以画出图像:(如下图)

可以求出递推式：
==$dp_{i, j} = (min || max)(dp_{i, j-1}, dp_{i+2^{j-1}, j-1})$==

预处理

void RMQ_intn() {
	for (int i = 1; i <= n; i++) {
		dp[i][0] = a[i];
	}
	int t = log(n) / log(2) + 1;
	for (int j = 1; j < t; j++) {
		for (int i = 1; i <= n - (1 << j) + 1; i++) {
			dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
		}
	}
} 

查询

int RMQ_query(int l, int r) {
	int k = log(r - l + 1) / log(2);
	return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}