写在前面：

　　记录了个人的学习过程，同时方便复习

• Sparse Table

  　　有些情况，需要反复读取某个指定范围内的值而不需要修改

  　　逐个判断区间内的每个值显然太浪费时间

  　　我们希望用空间换取时间

  　　ST表就是为此存在的

  　　在一维二维甚至三维中，利用动态规划的思想，将区域反复切割直到不能再分

  　　每一次切割产生的范围都可以存储想要的值：

  　　　　在生成时找好获得值的方法

  　　　　查询时找好获取值得关系

  　　在储存时，由于分割总是分成两半(横着来一下，竖着来一下就是四段)

  　　利用这个性质，就能高效的用2k或者2kn，2km表示每个分割区域的长度(面积)

  　　而在实现ST表的功能时，是将以上内容倒着进行的

  　　下面的代码仅仅是实现查询范围最大值

  　　若想查询范围最小值，对于二维的情况，可能会遇到一个矩阵没有填满的情况，取到了0

  　　这种情况需要特判一下

  　　同理，范围最大公因数，最小公倍数也需要特判

  　　但是最大值，差，和这种有没有多出来的0都一样的，就不必特判了

(这一点在二维的矩阵树里也有体现)

　　一维Sparse Table，区间类动态规划

C++：

1 #include
2 #define re register
3
4 using namespace std;
5
6 const int MAXN=100010;
7 int n,f[MAXN][31],Ql,Qr;
8 //f[左端点][2^k]
9 //区间[左端点][左端点+2^k-1]
10
11 inline int C_max(int a,int b){return a>b? a:b;}
12
13 int RMQ(int l,int r){
14 int t=0;//需要一个t使得2^k>=(r-l+1),2^k<(r-l+1),即两个2^t长度能覆盖区间
15 while((1<<(t+1))<=(r-l+1)) t++;//直到2^(t+1)就比总长度还要大了
16 return C_max(
17 f[l ][t],
18 f[r-(1<<t)+1][t]
19 );
20 }
21
22 int main(int argc,char *argv[],char *enc[])
23 {
24 scanf("%d",&n);
25
26 for(re int i=1;i<=n;++i)
27 scanf("%d",&f[i][0]);
28
29 for(re int k=1;(1<<k)<=n;++k)
30 for(re int i=1;i+(1<<k)-1<=n;++i)
31 f[i][k]=C_max(//每段长度均为2^(k-1)
32 f[i ][k-1],
33 f[i+(1<<(k-1))][k-1]
34 );
35
36 while(scanf("%d%d",&Ql,&Qr)==2)
37 printf("%d\n",RMQ(Ql,Qr));
38
39 return 0;
40 }
41 /*
42 将区间
43 (i,i+2^k-1)分成
44
45 (i,i+2^(k-1)-1)
46 (i+2^(j-1),i+2^k-1)
47 两部分
48 */

Java：

1 import java.io.*;
2 import java.util.*;
3
4 class pony{
5
6 static int MAXN=100010;
7 static int n,Ql,Qr;
8 static int[][] f=new int[MAXN][31];
9 //f[左端点][2^k]
10 //区间[左端点][左端点+2^k-1]
11
12 static int C_max(int a,int b){return a>b? a:b;}
13
14 static int RMQ(int l,int r){
15 int t=0;//需要一个t使得2^k>=(r-l+1),2^k<(r-l+1),即两个2^t长度能覆盖区间
16 while((1<<(t+1))<=(r-l+1)) t++;//直到2^(t+1)就比总长度还要大了
17 return C_max(
18 f[l ][t],
19 f[r-(1<<t)+1][t]
20 );
21 }
22
23 public static void main(String[] args) throws Exception {
24
25 Scanner cin=new Scanner(System.in);
26 n=cin.nextInt();
27
28 for(int i=1;i<=n;++i)
29 f[i][0]=cin.nextInt();
30
31 for(int k=1;(1<<k)<=n;++k)
32 for(int i=1;i+(1<<k)-1<=n;++i)
33 f[i][k]=C_max(//每段长度均为2^(k-1)
34 f[i ][k-1],
35 f[i+(1<<(k-1))][k-1]
36 );
37
38 Ql=cin.nextInt();
39 Qr=cin.nextInt();
40
41 System.out.println(RMQ(Ql,Qr));
42 }
43 }

　　二维Sparse Table，矩阵类动态规划

C++：

1 #include
2 #define re register
3
4 using namespace std;
5
6 const int MAXN=1010,MAXM=1010;
7 int n,m,f[MAXN][MAXN][15][15],qx1,qy1,qx2,qy2;
8 //f[y1][x1][km][kn]
9 //矩阵(x1,y1)(x1+2^kn-1,y1+2^km-1)
10
11 inline int C_max(int a,int b){return a>b? a:b;}
12 int C_max4(int a,int b,int c,int d){return C_max(C_max(C_max(a,b),c),d);}
13
14 int RMQ(int x1,int y1,int x2,int y2){
15 int tm=0,tn=0;
16 while((1<<(tm+1))<=(y2-y1+1)) ++tm;
17 while((1<<(tn+1))<=(x2-x1+1)) ++tn;
18 return C_max4(
19 f[y1 ][x1 ][tm][tn],
20 f[y2-(1<<tm)+1][x1 ][tm][tn],
21 f[y1 ][x2-(1<<tn)+1][tm][tn],
22 f[y2-(1<<tm)+1][x2-(1<<tn)+1][tm][tn]
23 );
24 }
25
26 int main(int argc,char *argv[],char *enc[])
27 {
28 scanf("%d%d",&n,&m);
29
30 for(re int i=1;i<=m;++i)
31 for(re int j=1;j<=n;++j)
32 scanf("%d",&f[i][j][0][0]);
33
34 /*
35 当某一维长度为1时不好处理，单独拿出来处理
36 */
37
38 for(re int km=1;(1<<km)<=m;++km)
39 for(int i=1;i+(1<<km)-1<=m;++i)
40 for(int j=1;j<=n;++j)
41 f[i][j][km][0]=C_max(f[i][j][km-1][0],f[i+(1<<(km-1))][j][km-1][0]);
42
43 for(re int kn=1;(1<<kn)<=n;++kn)
44 for(int i=1;i<=m;++i)
45 for(int j=1;j+(1<<kn)-1<=n;++j)
46 f[i][j][0][kn]=C_max(f[i][j][0][kn-1],f[i][j+(1<<(kn-1))][0][kn-1]);
47
48 for(re int km=1;(1<<km)<=m;++km)
49 for(re int kn=1;(1<<kn)<=n;++kn)
50 for(re int i=1;i+(1<<km)-1<=m;++i)
51 for(re int j=1;j+(1<<kn)-1<=n;++j)
52 f[i][j][km][kn]=C_max4(//每次平分矩形，小矩形长度为2^(j-1),高为2^(i-1)
53 f[i ][j ][km-1][kn-1],
54 f[i+(1<<(km-1))][j ][km-1][kn-1],
55 f[i ][j+(1<<(kn-1))][km-1][kn-1],
56 f[i+(1<<(km-1))][j+(1<<(kn-1))][km-1][kn-1]
57 );
58
59 while(scanf("%d%d%d%d",&qx1,&qy1,&qx2,&qy2)==4)
60 printf("%d\n",RMQ(qx1,qy1,qx2,qy2));
61
62 return 0;
63 }
64 /*
65 将矩阵
66 (j ,i ,j+2^k-1 ,i+2^k-1 )分成
67
68 (j ,i ,j+2^(k-1)-1,i+2^(k-1)-1)
69 (j ,i+2^(k-1)-1,j+2^(k-1)-1,i+2^k-1 )
70 (j+2^(k-1),i ,j+2^k-1 ,i+2^(k-1)-1)
71 (j+2^(k-1),i+2^(k-1)-1,j+2^k-1 ,i+2^k-1 )
72 四部分
73 */

Java：

1 import java.io.*;
2 import java.util.*;
3
4 class pony{
5
6 static int MAXN=1010,MAXM=1010;
7 static int n,m,qx1,qy1,qx2,qy2;
8 static int[][][][] f=new int[MAXN][MAXN][15][15];
9 //f[y1][x1][km][kn]
10 //矩阵(x1,y1)(x1+2^kn-1,y1+2^km-1)
11
12 static int C_max(int a,int b){return a>b? a:b;}
13 static int C_max4(int a,int b,int c,int d){return C_max(C_max(C_max(a,b),c),d);}
14
15 static int RMQ(int x1,int y1,int x2,int y2){
16 int tm=0,tn=0;
17 while((1<<(tm+1))<=(y2-y1+1)) ++tm;
18 while((1<<(tn+1))<=(x2-x1+1)) ++tn;
19 return C_max4(
20 f[y1 ][x1 ][tm][tn],
21 f[y2-(1<<tm)+1][x1 ][tm][tn],
22 f[y1 ][x2-(1<<tn)+1][tm][tn],
23 f[y2-(1<<tm)+1][x2-(1<<tn)+1][tm][tn]
24 );
25 }
26
27 public static void main(String[] args) throws Exception {
28
29 Scanner cin=new Scanner(System.in);
30 n=cin.nextInt();
31 m=cin.nextInt();
32
33 for(int i=1;i<=m;++i)
34 for(int j=1;j<=n;++j)
35 f[i][j][0][0]=cin.nextInt();
36
37 /*
38 当某一维长度为1时不好处理，单独拿出来处理
39 */
40
41 for(int km=1;(1<<km)<=m;++km)
42 for(int i=1;i+(1<<km)-1<=m;++i)
43 for(int j=1;j<=n;++j)
44 f[i][j][km][0]=C_max(f[i][j][km-1][0],f[i+(1<<(km-1))][j][km-1][0]);
45
46 for(int kn=1;(1<<kn)<=n;++kn)
47 for(int i=1;i<=m;++i)
48 for(int j=1;j+(1<<kn)-1<=n;++j)
49 f[i][j][0][kn]=C_max(f[i][j][0][kn-1],f[i][j+(1<<(kn-1))][0][kn-1]);
50
51 for(int km=1;(1<<km)<=m;++km)
52 for(int kn=1;(1<<kn)<=n;++kn)
53 for(int i=1;i+(1<<km)-1<=m;++i)
54 for(int j=1;j+(1<<kn)-1<=n;++j)
55 f[i][j][km][kn]=C_max4(//每次平分矩形，小矩形长度为2^(j-1),高为2^(i-1)
56 　　f[i ][j ][km-1][kn-1],
57 　　f[i+(1<<(km-1))][j ][km-1][kn-1],
58 　　f[i ][j+(1<<(kn-1))][km-1][kn-1],
59 　　f[i+(1<<(km-1))][j+(1<<(kn-1))][km-1][kn-1]
60 　　);
61
62 qx1=cin.nextInt();
63 qy1=cin.nextInt();
64 qx2=cin.nextInt();
65 qy2=cin.nextInt();
66
67 System.out.println(RMQ(qx1,qy1,qx2,qy2));
68 }
69 }