ST表

引入

$\text{RMQ}$ 问题

$\text{RMQ}$ 是英文 $\text{Range Maximum/Minimum Query}$ 的缩写，表示区间最大（最小）值。一般可用 $\text{ST} $ 表、线段树等数据结构解决。

可重复贡献问题

对于一个运算 $\text{opt}$ ，如果满足 $x \text{ opt } x=x$，则对应的区间询问就是一个可重复贡献问题。例如最大值有 $\max(x,x)=x$，最大公约数有 $\gcd(x,x)=x$，所以 $\text{RMQ}$ 和区间 $\text{GCD}$ 就是一个可重复贡献问题；而区间和就不具有这个性质，$x+x=2x$。

$\text{ST}$ 表

$\text{ST}$ 表的特点

对于一个静态数组，给出 $Q$ 次询问，每次询问区间 $[l,r]$ 的最大值，最暴力的方法是每次询问都遍历区间 $[l,r]$，时间复杂度最坏为 $O(Qn)$。
对于 $\text{RMQ}$ 问题，$\text{ST}$ 表通过 $O(n\log n) $的预处理，使得 $\text {RMQ}$ 问题的查询在 $O(1)$ 内完成，但是这同时意味着$\text{ST}$ 表有不可进行修改操作的缺点。
对于一个可重复贡献问题，$\text{opt}$ 必须同时满足结合律才能使用 $\text{ST}$ 表求解，这一点是和线段树类似的。

倍增思想

$\text{ST}$ 表的预处理是通过倍增思想实现的。下面以 $\text{RMQ}$ 为例阐述其实现过程。
给定一个数列$\{a_n\}$。定义 $f[i][j]$ 表示区间 $\left[i,i+2^j-1\right]$ 的最大值。
根据定义式，显然有 $f[i][0]=a[i]$；类似树上倍增的思想，有递推式 $f[i][j]=\max(f[i][j-1],f[i+2^{j-1}][j-1])$。
$f[i][j-1]$ 表示区间 $[i,i+2^{j-1}-1]$ 的最大值；$f[i+2^{j-1}][j-1]$ 表示区间 $[i+2^{j-1},i+2^j-1]$ 的最大值，两者覆盖整个区间 $\left[i,i+2^j-1\right]$ 。

查询 $\text{RMQ}$

我们查询两个区间$[l,l+2^s-1]$，$[r-2^s+1,r]$（即 $f[l][s],f[r-2^s+1][s]$），其中 $s=\lfloor \log_2(r-l+1)\rfloor$。两个区间的交集非空，两个区间的并集正是区间 $[l,r]$。因此 $[l,r]$ 区间的最大值为 $\max(f[l][s],f[r-2^s+1][s])$。正是因为运算 $\max$ 满足结合律和可重复贡献性，以上的分析是正确的。

洛谷 P3865 【模板】ST表 $\looparrowright$

题目描述

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 $N$, $M$ 分别表示数列的长度和询问的个数。
第二行包含 $N$ 个整数（记为 $a_i$），依次表示数列的第 $i$ 项。
接下来 $M$行，每行包含两个整数 $l_i, r_i$，表示查询的区间为 $[ l_i, r_i]$。

输出格式

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

输入输出样例

输入 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出 #1

9
9
7
7
9
8
7
9

说明/提示

对于 $30\%$ 的数据，满足： $1 \leq N, M \leq 10$
对于 $70\%$ 的数据，满足：$1 \leq N, M \leq {10}^5$
对于 $100\%$ 的数据，满足：$1 \leq N \leq {10}^5$, $1 \leq M \leq 2 \times {10}^6$, $a_i \in [0, {10}^9]$, $1 \leq l_i \leq r_i \leq N$

代码

#include<cstdio>
#include<algorithm>
#define N 100002
using namespace std;
int a[N];
int _log2[N];
int f[N][31];
int n,m;
/*预处理以2为底的对数值（向下取整）*/
void pre()
{
	_log2[1]=0;
	int i;
	for(i=2;i<N;i++) _log2[i]=_log2[i>>1]+1;
}
/*-------ST表初始化------*/
void init()
{
	int i,j;
	for(i=1;i<=n;i++) f[i][0]=a[i];//边界值
	for(j=1;(1<<j)<=n;j++)
	{
		for(i=1;i+(1<<j)-1<=n;i++)
		{
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int i;
	pre();
	for(i=1;i<=n;i++) scanf("%d",a+i);
	init();
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int s=_log2[r-l+1];
		//查询两个区间
		printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));
	}
	return 0;
}

二维 $\text{RMQ}$

给定一个 $m×n$ 的矩阵，$Q$ 次询问，每次询问以 $(r1,c1)$ 为左上角，$(r2,c2)$ 为右下角的最大值。

问题分析

暴力方法遍历矩阵的时间复杂度为 $O(Qmn)$。如果用 $m$ 棵线段树或者树状数组来维护每行区间最大值，最坏时间复杂度为 $O(mn\log n+Qm\log n)$。
既然是静态询问，我们可以用 二维 $\text {ST}$ 表处理这样的二维 $\text{RMQ} $ 问题。

二维 $\text{ST}$ 表

预处理

对于一个矩阵 $a_{mn}$，定义 $f[i][j][k][l]$ 为以坐标 $(i,j)$ 为左上角，以坐标 $(i+2^k-1,j+2^l-1)$ 为右下角的矩阵的最大值。预处理的时间复杂度为 $O(mn\log m\log n)$。

对于一块以坐标 $(i,j)$ 为左上角，以坐标 $(i+2^k-1,j+2^l-1)$ 为右下角的区域，如上图横着劈成两半，得到两块区域：以坐标 $(i,j)$ 为左上角 ，以坐标 $(i+2^k-1,j+2^{l-1})$ 为右下角的上半部分；以坐标 $ (i,j+2^{l-1})$ 为左上角，以坐标 $(i+2^k-1,j+2^l-1)$ 为右下角的下半部分。将两部分的最大值合并即可得到整个区域的最大值。
下面直接给出状态转移方程
$f[i][j][k][l]=\max\left(f[i][j][k][l-1],f[i][j+2^{l-1}][k][l-1]\right)$
$f[i][j][k][l]=\max\left(f[i][j][k-1][l],f[i+2^{k-1}][j][k-1][l]\right)$

查询

对于一个子矩阵，设左上角坐标为 $(r_1,c_1)$，右下角为 $(r_2,c_2)$，可以通过预处理的二维 $\text{ST}$ 表，将其分成四部分查询。

四个部分分别为图中 $W_1(A,E,F,G),W_2(H,B,J,I),W_3(M,L,K,C),W_4(O,P,D,N)$ 。
令 $p=\lfloor \log(r_2−r_1+1)\rfloor,q=\lfloor\log(c_2−c_1+1)\rfloor$，则：

${ans=\max\displaystyle {\begin{cases}f[r_1][c_1][p][q]&W_1\\f[r_2-2^p+1][c_1][p][q]&W_2\\f[r_1][c_2-2^q+1][p][q]&W_3\\f[r_2-2^p+1][c_2-2^q+1][p][q]&W_4\end{cases}}}$

HDU 2888 Check Corners $\looparrowright$

Problem Description

Paul draw a big $m\times n$ matrix $A$ last month, whose entries $A_ {i j } $ are all integer numbers $( 1\le i \le m, 1\le j\le n )$. Now he selects some sub-matrices, hoping to find the maximum number. Then he finds that there may be more than one maximum number, he also wants to know the number of them. But soon he find that it is too complex, so he changes his mind, he just want to know whether there is a maximum at the four corners of the sub-matrix, he calls this “Check corners”. It’s a boring job when selecting too many sub-matrices, so he asks you for help. (For the “Check corners” part: If the sub-matrix has only one row or column just check the two endpoints. If the sub-matrix has only one entry just output “yes”.)

Input

There are multiple test cases.
For each test case, the first line contains two integers $m, n$ $(1 \le m, n \le 300)$, which is the size of the row and column of the matrix, respectively. The next $m$ lines with $n$ integers each gives the elements of the matrix which fit in non-negative $32$-bit integer.
The next line contains a single integer $Q$ $(1\le Q \le 1000000)$, the number of queries. The next $Q$ lines give one query on each line, with four integers $r_1, c_1, r_2, c_2$ $(1 \le$ $r_1$$\le$ $r_2$ $\le m$, $1$ $\le$ $c_1$$\le$ $c_2$$\le$$ n)$, which are the indices of the upper-left corner and lower-right corner of the sub-matrix in question.

Output

For each test case, print $Q$ lines with two numbers on each line, the required maximum integer and the result of the “Check corners” using “yes” or “no”. Separate the two parts with a single space.

Sample Input

4 4
4 4 10 7
2 13 9 11
5 7 8 20
13 20 8 2
4
1 1 4 4
1 1 3 3
1 3 3 4
1 1 1 1

Sample Output

20 no
13 no
20 yes
4 yes

Translation

给定一个 $m×n$ 的矩阵，$Q$ 次询问，每次询问以 $(r_1,c_1)$ 为左上角，$(r_2,c_2)$ 为右下角的区域的最大值，并判断最大值是否在边界的四个点上取到。

Code

#include<algorithm>
#include<cstdio>
#define N 305
using namespace std;
int m,n,q;
int f[N][N][9][9];
int _log2[N],a[N][N];
/*预处理以2为底的对数*/
void pre()
{
	int i;
	_log2[1]=0;
	for(i=2;i<N;i++) _log2[i]=_log2[i>>1]+1;
}
/*---二维ST表初始化---*/
void init()
{
	int i,j;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			f[i][j][0][0]=a[i][j];//边界值
		}
	}
	int l,k;
	for(k=0;(1<<k)<=m;k++)
	{
		for(l=0;(1<<l)<=n;l++)
		{
			if(!k&&!l) continue;//该情况已经赋值
			for(i=1;i+(1<<k)-1<=m;i++)
			{
				for(j=1;j+(1<<l)-1<=n;j++)
				{
					//状态转移
					if(l) f[i][j][k][l]=max(f[i][j][k][l-1],f[i][j+(1<<l-1)][k][l-1]);
					else f[i][j][k][l]=max(f[i][j][k-1][l],f[i+(1<<k-1)][j][k-1][l]);
				}
			}
		}
	}
}
int query(int x1,int y1,int x2,int y2)
{
	int p=_log2[x2-x1+1];
	int q=_log2[y2-y1+1];
	//查询四个区域
	return max({f[x1][y1][p][q],f[x1][y2-(1<<q)+1][p][q],f[x2-(1<<p)+1][y1][p][q],f[x2-(1<<p)+1][y2-(1<<q)+1][p][q]});
}
int main()
{
	pre();
	while(~scanf("%d%d",&m,&n))
	{
		int i,j;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++) 
			{
				scanf("%d",&a[i][j]);
			}
		}
		init();
		int q;
		scanf("%d",&q);
		while(q--)
		{
			int r1,c1,r2,c2;
			scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
			int ans=query(r1,c1,r2,c2);
			printf("%d ",ans);
			//判断是否在边界上的四个点取到最大值
			if(ans==a[r1][c1]||ans==a[r1][c2]||ans==a[r2][c2]||ans==a[r2][c1]) puts("yes");
			else puts("no"); 
		}
	}
	return 0;
}