首页 > 代码库 > 说一说ST表 讲一讲水题
说一说ST表 讲一讲水题
ST表
一、算法介绍
如何快速求解RMQ问题呢？暴力复杂度O(n)，线段树复杂度O(n)~O(logn)，要是数据规模达到10^7或者更高呢？我们需要一种可以做到O(1)查询的算法，这时就可以用到ST表。
我们用 f[i][j] 表示从 j 位置开始往右 2^i 个数内的最大值，用 g[i][j] 表示从j位置开始往左 2^i 个数内的最大值。所以 f[0][j] , g[0][j] 就为 j 位置上的数，可以在预处理中O(n)处理掉。
接下来我们要求出每个位置的每个 2^i 区间的最大值。可以简单想到， f[1][j] = max( f[0][j] , f[0][j+1] ) , f[2][j] = max( f[1][j] , f[1][j+2]) , f[3][j] = max( f[2][j] , f[2][j+4] ) , ...... , 可以得出，f[i][j] = max( f[i-1][j] , f[i-1][j+(1<<(i-1))] ) , 同理可得， g[i][j]= max( g[i-1][j] , g[i-1][j-(1<<(i-1))] )。
对于每个查询有左端点L和右端点R，对于左端点L，从L开始能覆盖的最广而不超过右端点的倍增次数为log2(R-L+1)，从右端点开始能覆盖的最广而不超过右端点的倍增次数也为log2(R-L+1)，所以在[L,R]范围内最大值就为 max( f[log2(R-L+1)][L] , g[log2(R-L+1)][R] ) ，这样我们就做到了O(1)查询。
二、水题/裸题
bzoj1699
Description
每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.
Input
* 第一行: N 和 Q. * 第2..N+1行: 第i+1行是第i头牛的身高.
* 第N+2..N+Q+1行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从A到B的所有牛.
Output
*第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.
Sample Input
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
3
0
题解：用ST表算出各个区间的最大值、最小值即可。
AC代码：（写复杂了但也懒得改了）
1 #include <stdio.h> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 int N,Q; 6 int h[50010]; 7 int to_r_max[16][50010],to_l_max[16][50010]; 8 int to_r_min[16][50010],to_l_min[16][50010]; 9 int main(){10 scanf("%d%d",&N,&Q);11 for(int i=1;i<=N;++i) scanf("%d",&h[i]);12 for(int i=1;i<=N;++i) to_r_max[0][i]=to_l_max[0][i]=to_r_min[0][i]=to_l_min[0][i]=h[i];13 for(int i=1;i<=log2(N);++i)14 for(int j=1;j<=N;++j){15 to_r_max[i][j]=max(to_r_max[i-1][j],to_r_max[i-1][j+(1<<(i-1))]);16 to_r_min[i][j]=min(to_r_min[i-1][j],to_r_min[i-1][j+(1<<(i-1))]);17 to_l_max[i][j]=max(to_l_max[i-1][j],to_l_max[i-1][j-(1<<(i-1))]);18 to_l_min[i][j]=min(to_l_min[i-1][j],to_l_min[i-1][j-(1<<(i-1))]); 19 }20 for(int i=1;i<=Q;++i){21 int l,r;22 scanf("%d%d",&l,&r);23 int lenn=r-l+1;24 int h=max(to_r_max[int(log2(lenn))][l],to_l_max[int(log2(lenn))][r]);25 int s=min(to_r_min[int(log2(lenn))][l],to_l_min[int(log2(lenn))][r]);26 printf("%d\n",h-s);27 }28 return 0;29 }
说一说ST表 讲一讲水题