±1 RMQ

缘起

【1】和【2】分别给出了RMQ问题的ST解法（本质就是打表DP）和线段树解法. 这里给出±1RMQ问题的O(N)~O(1)解法. 即算法初始化要 O(N)， 而解答每次询问都只需要O(1)的时间（很快）

这种±1 RMQ 问题的应用场景是什么? 在RMQ的标准解法——O(n)转笛卡尔树， 最后转该树上的LCA问题中有用.

分析

所谓±1 RMQ问题指的是常规RMQ中涉及的数组相邻元素相差不是1就是-1.

本文以 求极大为例.

±1RMQ的想法是, 使用 L = logN/2 （这里的log是以2为底的对数）为步长分割整个数组. 则得到 N/L 个区间.

则每个区间其实都是一步+1,或者一步-1构成的序列. 其实就好像是五线谱一样. 五线谱的下一个音符比它前面一个音符高一个位或者第一个位.

注意，要明确我们想解决的问题——就是要得到任何一个区间[i,j]内部的最大值的索引，注意，我们只要索引.

我们采用分治的策略来解决±1RMQ。 将整个区间分成L的一小块一小块（每一块都是闭区间，长度为L, 不能整除就取余）. 则±1RMQ问题就分治为了块内RMQ和块间RMQ.

块间RMQ是简单的——例如要求下图中i和j的最大值索引. 则只需要求出

[i,b]和[b,j]两个区间的最大者之间再取大即可（如果跨越多个块的话，其实还是一个N/L的数组的RMQ问题, 使用ST处理， 复杂度是O(N/L*log(N/L))<=O(N/L*logN)=O(N), 所以也是线性时间内可以完成的任务）. 所以如果我们块内RMQ搞定了的话，则块间RMQ在O(1)时间内是可以搞定的. 而块内RMQ需要多长时间呢? 注意，这里需要用到±1RMQ的本质——相邻元素之差不是1就是-1. 这样的话，则其实一块L长度的区间高高低低的次序只有 2^L=sqrt(N) 种. 而每一种我们都可以通过暴力枚举i和j, 算出[i,j]中最大值的索引（我们RMQ问题的着眼点是求索引，所以这段高高低低的折线的起点可以忽略. 本质不同只有+1的个数和-1的个数的不一样）. 这个过程需要耗费的时间是 L（枚举i）*L（枚举j）*L（求[i,j]内最大值的索引）sqrt(N)=O((logN)^3\sqrt(N))。 其实用到的事实就是一段±1高高低低的折线，不论它的起始值是多大，它的任何子区间的最大值索引是已经定下来了的. 也就是我们要的是一个相对的结果，和绝对大小无关

也就是初始化需要O(N^(1/2+alpha))时间，alpha是可以任意小的正数. 然后开始扫描整个区间. 扫描一段L长度的区间完毕之后应该就知道这段区间对应是哪种±1序列了，则O(1)时间就知道这段区间内任意子区间内的极大值的索引. 则块内RMQ问题就在O(N)+O(sqrt(N)*(logN)^3)=O(N)时间内预热完毕. 这个时间是线性的.

所以±1RMQ问题是 O(N)~O(1)的. 下面代码实现（讲真比单纯的ST要复杂很多，就为了初始化O(nlogn)降低到O(n),值得么?）

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
#include "stdafx.h"
#include <stdio.h>
#include <cmath>
#include <algorithm>
#define LOCAL

using namespace std;

const int MAX_N = 105, MAX_L = 20, MAX_SQRT_N = 20, INF = -0x3f3f3f3f; // MAX_N是数组的最大长度,MAX_L=logMAX_N/2, MAX_SQRT_N = sqrt(MAX_N), 所以即便数组长度为1000w, 则ans的第一维度也被压缩到了1w这个级别, 所以算法的实用性还是比较高的

int n,a[MAX_N],L, ans[MAX_SQRT_N][MAX_L][MAX_L], ll[MAX_L], s[MAX_N], top, st[MAX_L][MAX_N]; // 参与±1 RMQ问题的数组, n是实际的长度,L是块的长度, ans[x] 是第x个±1序列的结果. [i][j]是这个序列的[i,j]区间上的最大值,ll是长度为L的数组,s存放该±1序列的哈希值（﹢1为1，-1为0）

void dfs(int step, int x) // 决定 长度为L的 ±1序列的 [i,j] 的值, 现在决定到了 索引为i的元素的值（到底是+1还是-1）, 当前已经是x了
{
	if (step>=L) // 得到了一个长度为L的 ±1序列ans[x]（注意，正负1只是相邻两个的差值, L个元素之间的差值为L-1个, 假设这个L片段的初始起点是0）, 现在要决定它的ans[x][i][j],即[i,j]区间上的最大值的索引, for 0<=i<=j<L
	{
		for (int i = 0; i< L; i++) // 暴力枚举 区间[i,j]
		{
			for (int j = i; j<L; j++)
			{
				int _max = i; // _max 是[i,j]上的最大值索引
				for (int k = i; k<=j; k++) if (ll[k]>ll[_max]) _max = k;
				ans[x][i][j] = _max;
			}
		}
		return;
	}
	ll[step] = ll[step-1]+1; // 这一步决定 是 +1, 当然如果是决定step[0]的话, 则就是1, 因为我们将这个区间的起始值设置为0
	dfs(step+1, (x<<1)+1);
	ll[step] = ll[step-1]-1; // 这一步决定 是 -1
	dfs(step+1, x<<1);
}

void _st() // st算法处理s, st这个二维数组的最终目的是O(1)时间快速回答块间询问, 所以 st[0] 存放的是各个块的最大值的索引下标.
{
	for (int i = 0; i<top; i++)
	{
		st[0][i] = ans[s[i]][0][L-1]+i*L;
	}
	int k = 1;
	while(1<<k<=top) // 构筑第k层
	{
		for (int i = 0; i< top; i++)
		{
			if (i+(1<<(k-1))>=top) // 只能选它
			{
				st[k][i] = st[k-1][i];
			}
			else
			{
				if (a[st[k-1][i]]>a[st[k-1][i+(1<<(k-1))]])
				{
					st[k][i] = st[k-1][i];
				}
				else
				{
					st[k][i] = st[k-1][i+(1<<(k-1))];
				}
			}
		}
		k++;
	}
}

void rmq_warmup()  // 确切讲, 是rmq算法的预热——包括两部分, 块内查询的预热和块间查询的预热
{
	while((1<<L)<=n) L++; // 最后 2^L>n, 则 L>0
	if (L==1) L++; // 不然的话, L/2就是0
	L>>=1; // 则L就是块的长度
	ll[0]= 0; // L片段的起点为0
	dfs(1,0);
	for (int i = 0,x;i<n;i+=L) // 开始扫描整个区间
	{
		x = 0; // 哈希值
		int j;
		for (j = i; j<i+L-1&&j<n-1;j++) ~(a[j+1]-a[j])?(x=(x<<1)|1):(x<<=1);
		x<<(i+L-1-j); // 如果这是一个完整的L长度的片段的话, 则j最后一定会增加到 i+L-1，否则就不是一个完整的L片段, 由于求的是极大RMQ问题, 所以让后面的操作全部是-1, 这样的话, 极大值只可能在前面的片段中存在. 而为-1 的操作就是<<1, 所以这里移位这么多
		s[top++] = x; // 缓存这个片段的哈希值
	}
	// 使用st算法在O(N)时间内预处理s
	_st();
}

int rmq_ans(int i,int j) // O(1)时间内回答 [i,j]内最小值
{
	int _max_l, _max, _max_r, _i, _j,_max_l_index, _max_r_index; //  _max_l是左边的块内最大索引, _max 是中间的跨块的最大值索引(用st求[_i,_j]最大),_max_r是右边的块内最大索引,_max_l_index是左边块内最大的索引, _max_r_index是右边块内最大的索引
	_i = i/L+1;
	_max_l_index = i/L*L+ans[s[i/L]][i-i/L*L][L-1]; // 左边的块内最大对应的索引
	_max_l = a[_max_l_index]; // 左边的块内最大
	_j = j/L-1;
	_max_r_index = j/L*L+ans[s[j/L]][0][j-j/L*L];
	_max_r = a[_max_r_index]; // 右边的块内最大
	if (_i>_j) _max = INF; // [_i,_j]是块间最大问题的区间
	else
	{
		int k = 0;
		while((1<<k)<=_j-_i+1) k++; // 最后 1<<k>[_i,_j]区间长度, 但是 1<<(k-1)<=(_j-_i+1)
		_max = a[st[k-1][_i]] > a[st[k-1][_j-(1<<(k-1))+1]]?a[st[k-1][_i]]:a[st[k-1][_j-(1<<(k-1))+1]]; // 求出块间的最大值
	}
	return max(_max_l, max(_max, _max_r)); // 三者求最大就是此RMQ问题的答案.
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif // LOCAL
	scanf("%d", &n);
	for (int i = 0; i<n;i++) scanf("%d", a+i);
	rmq_warmup(); // O(n)时间算法预热
	int begin,end;
	while(~scanf("%d%d", &begin, &end))
	{
		if (begin>end) swap(begin,end);
		printf("a[%d,...,%d]内的最大值为%d\n",begin, end, rmq_ans(begin,end));  // O(1)时间算法解答, 注意, 这里没有求极大值的索引, 当然也完全可以不改变复杂度的情况下给出解答. 只是算法写起来比较复杂（完全可以实现的, 就是st记录的不是最大值,而是索引,还要考虑到L块的移位,甚是复杂,这种复杂不是思想上的,而是技术上的）.
	}
	return 0;
}
/*
测试数据
21
3 2 3 4 5 6 5 6 7 8 9 10 11 10 9 8 9 10 11 10 9
4 7
0 0
1 9
1 7
1 8
2 3
6 15
11 11
11 12
0 20
19 20
18 20
*/

最后形象的以下图表示±1 RMQ问题的解法（以最小RMQ为例）

参考

【1】https://yfsyfs.github.io/2019/07/15/RMQ/

【2】https://yfsyfs.github.io/2019/07/15/RMQ%E4%B9%8B%E7%BA%BF%E6%AE%B5%E6%A0%91%E8%A7%A3%E6%B3%95/