RMQ

缘起

【1】中给出了RMQ的线段树解法. 这里给出RMQ的ST算法（sparse-table），不论是线段树还是ST都属于在线算法. 关于在线算法和离线算法，参见【2】

分析

ST算法的本质就是打表DP. ST算法的本质可以使用下图表示

​ 图1

所以的确能做到O(1)回答询问，但是初始化的代价比线段树高，ST的初始化是O(nlogn)的, 而线段树的初始化代价是O(N)的，但是线段树的回答询问的代价是O(logN)的. 所以其实这么看来, ST算法比线段树还是略胜一筹的——O(1)毕竟难得.

下面以rmq求最大值为例. 注意这里为了能方便处理而不用理会越界问题，将原数组扩充了一倍，后半段全部是-INF，这样不影响求最大值. 也就是下面这样

​ 图2

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

using namespace std;

const int MAX_N = 20, INF = -0x3f3f3f3f; // 最多20个数

int a[MAX_N<<1] = {INF ,2,1,3,4,8,5,-1,19,-4,27,89,2,7}, st[MAX_N<<1][MAX_N<<1], n = 13; // 索引0不用于存储数据, 但是st的第一个索引用于保存层数, 所以还是要用的, st的第二个索引的0不用于保存数据

void build() // 构建st表
{
	for (int i = n+1; i<=(n<<1); i++) a[i] = INF; // 扩充， 见图2
	memcpy(st[0]+1, a+1, (n<<1)*sizeof(int)); // 内存复制, 效率比for高, 构建st表的第0层
	int k = 1;
	while(1<<k <= n) // 构建st表的第k层
	{
		memcpy(st[k]+n+1, st[k-1]+n+1, n*sizeof(int)); // 复制 INF， 构建st表的第k层的后半段——全是INF
		for (int i = 1; i<=n;i++) st[k][i]= max(st[k-1][i], st[k-1][i+(1<<(k-1))]); // 构建 st 表的第k层的前半段,第k层的st值恰好就等于k-1层的2个st值取大,即长度为2^k的区间的最大值=两个长度为2^(k-1)的区间的最大值取大
		k++;
	}
}

int rmq(int i, int j)
{
	int k = 0;
	while((1<<k)<=(j-i+1))k++; // 最后 2^k>[i,j]的长度,而2^(k-1)<=(j-i+1), 则k一定>=1, 于是我们要工作的地方在st表的第k层，即st的第一个索引是k-1的层
	return max(st[k-1][i], st[k-1][j-(1<<(k-1))+1]); // 见图2
}

int main()
{
	build();
	int i,j;
	while(~scanf("%d%d", &i, &j))
	{
		printf("%d\n", rmq(i,j));
	}
	return 0;
}

参考

【1】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/

【2】https://yfsyfs.github.io/2019/07/15/%E5%9C%A8%E7%BA%BF%E7%AE%97%E6%B3%95%E5%92%8C%E7%A6%BB%E7%BA%BF%E7%AE%97%E6%B3%95/