算法 ST表

思想（本质为dp）： 

题目AcWing1270. 数列区间最大值：

1270. 数列区间最大值 - AcWing题库 

输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y要求你说出 X到 Y这段区间内的最大数。

输入格式

第一行两个整数 N,M表示数字的个数和要询问的次数；

接下来一行为 N个数；

接下来 M行，每行都有两个整数 X,Y。

输出格式

输出共 M行，每行输出一个数。

数据范围

数列中的数字均不超过

输入样例：

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

输出样例：

5
8

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 100010,M = 20;

int st[N][M],a[N],lg2[N];
int n,m;

void init_st()
{
	for(int j = 0;(1 << j) <= n;j++)//区间长度
		for(int i = 0;i + (1 << j) - 1 < n;i++)//区间左右端点
			if(j == 0) st[i][j] = a[i];
			else st[i][j] = max(st[i][j-1],st[i + (1 << (j - 1))][j-1]);
}

void init_lg2()
{
	lg2[1] = 0;//lg2[x] = lg2[x/2] + lg2[2] = lg2[x/2] + 1; 
	for(int i = 2;i <= n;i++)//长度
		lg2[i] = lg2[i >> 1] + 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 0;i < n;i++)scanf("%d",&a[i]);
	init_st();
	init_lg2();

	for(int i = 0;i < m;i++)
	{
		int x = 0,y = 0;
		scanf("%d%d",&x,&y);
		x--,y--;
		int len = y - x + 1;
		int k = lg2[len];//k是下取整的结果，但：2 * 2^k >= len 
		//int k = log2(len);//用库函数算
		printf("%d\n",max(st[x][k],st[y - (1 << k) + 1][k]));
	}
	return 0;
}

题目AcWing1274. 奶牛排队：

1274. 奶牛排队 - AcWing题库

每天，农夫 John 的 N头牛总是按同一序列排队。

有一天，John 决定让一些牛玩一场飞盘比赛。

他准备找一群在队列中位置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。

John 准备了 Q个询问。

他想知道每一组里面最高和最矮的牛的身高差别。

输入格式

第一行包含两个整数 N,Q。

第二至第 N+1+1 行，第 i行是第 i 头牛的身高 ℎi；

第 N+2 至第 N+Q+1 行，每行两个整数 A 和 B，表示从 A 到 B 的所有牛。

牛的编号从 1 到 N。

输出格式

第一至第 Q 行，每行一个整数，表示对于询问的回答（即最高和最矮的牛的身高差）。

数据范围

输入样例：

6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出样例：

6
3
0

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 50010,M = 20;

int n,m;
int st_ma[N][M],st_mi[N][M],lg2[N],h[N];

void init_st()
{
	for(int j = 0;(1 << j) <= n;j++)
		for(int i = 1;i + (1 << j) - 1 <= n;i++)
			if(j == 0) st_ma[i][j] = st_mi[i][j] = h[i];
			else
			{
				st_ma[i][j] = max(st_ma[i][j-1],st_ma[i + (1 << (j-1))][j-1]);
				st_mi[i][j] = min(st_mi[i][j-1],st_mi[i + (1 << (j-1))][j-1]);
			}
}

void init_lg2()
{
	lg2[1] = 0;
	for(int i = 2;i <= n;i++)
		lg2[i] = lg2[i >> 1] + 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++) scanf("%d",&h[i]);
	init_st();
	init_lg2();
	
	for(int i = 0;i < m;i++)
	{
		int x = 0,y = 0;
		scanf("%d%d",&x,&y);
		int len = y - x + 1;
		int k = lg2[len];
		int ma = max(st_ma[x][k],st_ma[y - (1 << k) + 1][k]);
		int mi = min(st_mi[x][k],st_mi[y - (1 << k) + 1][k]);
		printf("%d\n",ma - mi);
	}
	return 0;
}