RMQ

发表于 更新于 分类于 阅读次数：

总结求各种 RMQ 的常用技巧和方法。
RMQ 真是流皮，每次深入思考都会有新的发现，所以有了新的发现会更新。

以下 n 表示数列的大小，q 表示询问的次数，均以最大值为例。

一般性普通做法

线段树当然是可以在线维护的，复杂度 \(O(n + qlogn)\) 。
甚至还可以支持单点修改或区间修改。

但是如果只是静态询问的话，可以用 ST 表预处理后 \(O(1)\) 在线处理询问，
复杂度 \(O(nlogn + q)\) 。

这两个做法烂大街了，是基础中的基础，不是本文讨论重点。

区间定长特殊做法

即所有的询问区间的长度都为与询问无关的定值 \(len\) 。
直接当做任意区间做，可以做到 \(O(n + qlogn)\) 或 \(O(nloglen + q)\) 。

这种情况下有更好理解的预处理方法，只需优先队列。
先把 \([1, l]\) 的数扔进优先队列里，之后不断把区间右移，
\([l, r]\) 右移的过程相当于加一个点 \(r + 1\) 并删掉点 \(l\) ，用优先队列维护即可。
复杂度 \(O(nlogn + q)\) 。

但这还不够，还有线性的预处理方法，用单调双端队列代替上面的优先队列。
同样是让区间不断右移，单调双端队列中的值是单调不增的， 那么最左边的值一定是最大值。
加点 \(r + 1\) 前维护单调性，删点 \(l\) 时判断是不是删的最大值， 如果是就删点最左边的点即可。
复杂度 \(O(n + q)\) 。

随机询问期望做法

这种情况下有个 \(O(n + q)\) 的在线做法。

考虑分块，设块的大小为 \(b\) ， \(O(n)\) 预处理每个块的最大值。

那么对于询问 \([l, r]\) ，若该区间跨过了多个块，问题就分为两个部分：

  1. 求跨过的块区间的最大值。
  2. 求两端点所在零散的块的最大值。

第一个问题就是个子问题，并且数据规模减小到了 \(O(\frac{n}{b})\) ，
为了保证询问 \(O(1)\) ，可以用上面一般性的普通做法提到的 ST 表，
就可以 \(O(\frac{n}{b} log\frac{n}{b})\) 进行预处理然后 \(O(1)\) 询问。

第二个问题端点所在零散的块是该块的一段前缀或者后缀，
只需 \(O(n)\) 对于每个块预处理前缀最大值和后缀最大值即可 \(O(1)\) 询问。

那么若询问区间在同一个块内呢？
自然是暴力扫，但是这样的复杂度是 \(O(b)\) 的。
但询问区间随机的情况下，不难得出两个端点在同一个块内的概率是 \(\frac{b}{n}\) 。
那么这种情况询问的期望复杂度是 \(O(\frac{b^2}{n})\) 的。

总复杂度 \(O(n + \frac{n}{b} log\frac{n}{b} + q + q \frac{b^2}{n})\) 。
当 \(b\) 至少为 \(O(logn)\) 时，预处理的 \(O(\frac{n}{b} log\frac{n}{b})\) 不超过 \(O(n)\) 。
当 \(b\) 至多为 \(O(\sqrt{n})\) 时，询问的 \(O(q \frac{b^2}{n})\) 不超过 \(O(q)\) 。
因此 \(b\) 的大小取 \(O(logn)\) 到 \(O(\sqrt{n})\) 之间即可。

另外，当 \(b = \sqrt{n}\) 时，块的个数也是 \(O(\sqrt{n})\) 的，
此时根本不需要 ST 表，直接 \(O(\sqrt{n}^2)\) 暴力预处理处理所有可能区间的最大值即可。
这样复杂度不变，常数可能还能小一点。

毒瘤活动

值得注意的是，虽然这个做法的复杂度仅适用于询问区间随机的情况，但是一般不会卡。

来点有意思的娱乐活动，考虑怎么卡掉它，以及怎么防止被出题人卡。

想要卡这个做法就要尽量让询问区间在一个块内，卡成 \(O(b)\) 的询问复杂度。
但在不知道块的大小的情况下，假设给一个区间长 \(len\) 的询问，实际块的大小为 \(b\) ，
那么两个端点在同一个块内的概率大概是 \(\frac{b-len+1}{b}\) ，期望复杂度就是 \(O(\frac{(b-len+1)len}{b})\) 。

现在出题人要在不知道 \(b\) 的情况下希望上面的复杂度尽量大，选手要在不知道 \(len\) 的情况下希望上面复杂度尽量小。
怎么感觉像博弈论

最坏的情况是 \(len = \frac{b}{2}\) 的时候，此时询问的期望复杂度为 \(O(\frac{b}{4})\) 。
选手希望预处理和询问的复杂度最大值最小，也就是让它们相等，此时 \(b\) 的最优取值大致为 \(2\sqrt{\frac{n}{q} logn}\) ，
这里说是“大致”，是因为为了方便计算将 \(O(log \frac{n}{b})\) 看做了 \(O(logn)\) 。
将 \(n, q\) 看做同阶的话，上述取值为 \(2\sqrt{logn}\) ，此时复杂度为 \(O(\frac{n\sqrt{logn}}{2})\) ，
也就是 \(O(n\sqrt{logn})\) ，得出结论，在询问区间非随机的情况下，该算法最优可以做到严格 \(O(n\sqrt{logn})\) 。

关键这算法常数小，还好写，取 b 为 \(O(\sqrt{logn})\) 的话，复杂度 \(O((n + q)\sqrt{logn})\) 在绝大多数情况都足够了。

另外，此时没必要维护块内前缀后缀最大值，因为块足够小，询问的时候对零散的块暴力扫就好了，复杂度不变。

一般性较优做法

自己 yy 出来的，权当过渡吧。

上面提到的 \(O((n + q)\sqrt{logn})\) 算法中，通过分块将问题规模缩小到了 \(\frac{n}{b}\) ，
然后对于这个规模的问题使用 ST 表，预处理复杂度近似看做 \(O(\frac{n}{b}logn)\) 。
而既然这是个子问题，为什么还要用 ST 表？能不能继续分块直到 ST 表的预处理复杂度在 \(O(n)\) 以内？

当然是可以的，这个时候块的大小又要取多少呢？
取 \(b = 2\) 就够了，这个时候，相当于从底层向上建线段树，
第一层有 \(n\) 个节点，第二层有 \(\frac{n}{2}\) 个节点，第三层有 \(\frac{n}{4}\) 个节点，
直到某一层只有 \(\frac{n}{logn}\) 个节点时，不再向上建线段树，而是用 ST 表维护这 \(\frac{n}{logn}\) 个点，
这样 ST 表的预处理就是 \(O(n)\) 的，而此时这个线段树的树高是 \(O(loglogn)\) 的。

总时间复杂度 \(O(n + qloglogn)\) ，事实上层数可以再少点，使得 ST 表预处理不严格 \(O(n)\) 而是与询问复杂度相当，
但这样的话最优的层数难以计算，在此不讨论。

毒瘤活动

从下向上建线段树太麻烦了，怕不是要写 zkw ，考虑从上向下建。
由于最上面一层有 \(\frac{n}{logn}\) 个节点，每个节点管辖的区间大小为 \(logn\) ，
继续考虑分块，以 \(b = logn\) 为块大小分块，那么就是块内直接建满的线段树，块间维护 ST 表。

卧槽怎么又回到前面的做法了

那么这个算法事实上就是通过线段树保证了块间查询严格 \(logb\) ，也就是 \(loglogn\) 。

既然这样，为什么一定要用线段树呢？在每个块内依然维护 ST 表，复杂度就是 \(O(nloglogn + q)\) 。

通过上面的各种讨论，相信读者已经明白分块 RMQ 的强大，以及线段树和 ST 表（尤其是后者）在 RMQ 的重要性。
分块什么这么多东西目的基本就是去平衡 ST 表 / 线段树的询问和预处理的复杂度。

update: 后来知道这玩意叫四个俄罗斯人算法 (Four Russian) 。

一般性标准做法

标准的 \(O(n + q)\) RMQ 。

离线的话可以建笛卡尔树将 RMQ 转换为 LCA ，然后用 Tarjan 处理。
明显的缺点是离线，并且空间开销较大。

在线的话，有一个经典的常用做法，还是建笛卡尔树转 LCA ，然后求出树的欧拉序转为 +-1 RMQ 。
而 +-1 RMQ 也是通过分块实现 \(O(n + q)\) 复杂度的，
利用的是 +-1 RMQ 的差分数组在每个块内只有 \(2^b\) 中可能，其中 \(b\) 是块大小，取 \(logn\) 。
整个过程较为复杂，在 OI 中实用性较低，具体做法留个坑，到时候再补。

这里重点介绍另一个同样能做到在线 + 线性的 RMQ 算法，并且相对于上面的做法更简单，常数也更优秀。

线性 RMQ

该算法改进自之前在随机数据下的分块 RMQ ，
注意到当块大小为 \(O(logn)\) 时，该算法唯一的瓶颈在于询问端点在同一个块内时需要暴力 \(O(logn)\) 扫。
单独考虑每个块，考虑优化询问端点在该块的情况。
其中块大小为 \(b = O(logn)\) 。

利用之前提到的单调队列做法，如果对于每个点暴力存下块的左端点到该点的单调递减队列，
那么对于询问 [l, r] ，拿出 r 上的单调队列，在单调队列上找到第一个不小于 l 的位置，该位置上的值即区间最大值。
由于单调队列的大小是 \(O(b)\) 即 \(O(logn)\) 的，该做法复杂度 \(O((n + q)logn)\) 。

但是该做法有很大优化空间，由于 \(b\) 足够小（一般认为它不超过字长 \(w\) ），完全可以将每个点的单调队列状压，
这样预处理的时空复杂度就降到了 \(O(n)\) 。
然后对于询问一个单调队列上第一个不小于 l 的位置，就是在一个二进制数 \(x\) 上询问第一个位数不小于 l 的 1 的位数。
这通过位运算和内置函数可以很好实现，只需将 \(x\) 右移 \(l mod b\) 位来去掉单调队列上小于 l 的位置，
然后通过 __builtin_ctz \(O(1)\) 找到第一个 1 的位置即可。
这样询问的复杂度就降到了 \(O(1)\) ，总复杂度 \(O(n + q)\) ，常数非常优秀。

完整实现

以 bzoj1699 为例，该题的 rank1 就是用了这个线性 RMQ 做法，本人常数大，但还是狗到了 rank6 。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <cmath>
#define debug(...) fprintf(stderr, __VA_ARGS__)

namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr, flg;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () {
		fwrite (obuf, 1, size_t(oS - obuf), stdout);
		oS = obuf;
	}
	inline void pc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template <class I>
	inline int gi (I &x) {
		for (f = 1, c = gc(); c != EOF && (c < '0' || c > '9'); c = gc()) if (c == '-') f = -1;
		for (flg = x = 0; c != EOF && c <= '9' && c >= '0'; c = gc()) flg = 1, x = x * 10 + (c & 15); x *= f;
		return flg || c != EOF;
	}
	template <class I>
	inline void print (I x) {
		if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) pc (qu[qr --]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}

struct {
	inline operator int () { int x; return io::gi(x), x; }
} read;

const int maxn = 50005, maxs = 20005, maxb = 80;
int a[maxn + maxb];
int highbit[maxs];
int stmax[maxs][maxb], stmin[maxs][maxb];
int premax[maxs][maxb], premin[maxs][maxb];
int sufmax[maxs][maxb], sufmin[maxs][maxb];
int quemax[maxs][maxb], quemin[maxs][maxb];
int stackmax[maxb], stackmin[maxb];

inline void chkmax(int &x, int y) {
	if(y > x) x = y;
}

inline void chkmin(int &x, int y) {
	if(y < x) x = y;
}

inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }

int main() {
	int n = read, q = read;
	int B = int(log2(n));
	int S = (n - 1) / B + 1;

	for(int b = 0; b < S; b ++)
		stmin[b][0] = 1000000000;

	for(int i = 0; i < n; i ++) {
		a[i] = read;
		chkmin(stmin[i / B][0], a[i]);
		chkmax(stmax[i / B][0], a[i]);
	}

	for(int b = S - 1; b >= 0; b --)
		for(int k = 1; b + (1 << k) - 1 < S; k ++) {
			stmin[b][k] = min(stmin[b][k - 1], stmin[b + (1 << (k - 1))][k - 1]);
			stmax[b][k] = max(stmax[b][k - 1], stmax[b + (1 << (k - 1))][k - 1]);
		}

	for(int b = 0; b < S; b ++) {
		int be = b * B;
		premin[b][0] = premax[b][0] = a[be];
		for(int k = 1; k < B; k ++) {
			premin[b][k] = min(premin[b][k - 1], a[be + k]);
			premax[b][k] = max(premax[b][k - 1], a[be + k]);
		}
		sufmin[b][B - 1] = sufmax[b][B - 1] = a[be + B - 1];
		for(int k = B - 2; k >= 0; k --) {
			sufmin[b][k] = min(sufmin[b][k + 1], a[be + k]);
			sufmax[b][k] = max(sufmax[b][k + 1], a[be + k]);
		}
	}

	for(int b = 0; b < S; b ++) {
		int be = b * B;
		int spmin = 0, nowmin = 0;
		int spmax = 0, nowmax = 0;
		for(int i = 0; i < B; i ++) {
			while(spmin and a[be + stackmin[spmin]] > a[be + i])
				nowmin ^= 1 << stackmin[spmin --];
			while(spmax and a[be + stackmax[spmax]] < a[be + i])
				nowmax ^= 1 << stackmax[spmax --];
			quemin[b][i] = (nowmin ^= 1 << (stackmin[++ spmin] = i));
			quemax[b][i] = (nowmax ^= 1 << (stackmax[++ spmax] = i));
		}
	}

	for(int i = 2; i <= S; i ++)
		highbit[i] = highbit[i >> 1] + 1;

	while(q --) {
		int l = read - 1;
		int r = read - 1;
		int L = l / B, R = r / B;
		int li = l % B, ri = r % B;

		int min = 1000000000, max = 0;
		if(L == R) {
			chkmin(min, a[l + __builtin_ctz(quemin[R][ri] >> li)]);
			chkmax(max, a[l + __builtin_ctz(quemax[R][ri] >> li)]);
		}
		else {
			chkmin(min, sufmin[L][li]);
			chkmin(min, premin[R][ri]);
			chkmax(max, sufmax[L][li]);
			chkmax(max, premax[R][ri]);
			int len = R - L - 1;
			int k = highbit[len];
			if(len) {
				chkmin(min, stmin[L + 1][k]);
				chkmin(min, stmin[R - (1 << k)][k]);
				chkmax(max, stmax[L + 1][k]);
				chkmax(max, stmax[R - (1 << k)][k]);
			}
		}

		/* printf("%d\n", max - min); */
		io::print(max - min);
		io::pc('\n');
	}
}