注：为方便描述算法 便于记忆 所以ST的代码用Pascal书写 见谅
RMQ，即Range Minimum/Maximum Query问题，给定一个区间，询问不同子区间的最值问题。
当询问次数较少时，朴素算法的时间尚可（暴力做法），k次询问，最坏情况是每次询问最大区间，时间复杂度O(kL)，其中k表示询问次数，L表示给定的区间长度。
随着询问次数的增加，朴素算法（应该可以认为是n² 级别的算法）就显得太慢了，因此可以很方便想出线段树做法，节点存储区间最值。那么此时k次查询，L的区间长度，可知时间复杂度为O(k logL)；L为定值，则log L为常数，随着k的增大线性增大，相比较朴素算法是大大优化了。
但是还不够。当 n过于大时，即使是线段树也不行。此时考虑ST（Sparse Table）算法。该算法的时间复杂度为两部分：预处理O(L logL)，查询则为O(1)。
（关于构造笛卡尔树的方法日后另写qwq）
ST方法的原理类似DP。比如说求[1,100]的最值，如果我能知道[1,64]的最值以及[37,100]的最值，那么总区间的最值，一定是两个分区间中的一个最值。
这个例子很方便理解ST。对于分区间继续拆分，直到出现长度为2的区间；此时长度为2的区间最值就是原序列中两个数的较大值。
运用倍增就可以完成拆分。
于是开始搭建：
1 begin 2 init; 3 readln(m); 4 for i:=1 to m do 5 begin 6 readln(head,tail); 7 if head>tail then 8 begin 9 temp:=head;10 head:=tail;11 tail:=temp;12 end;13 writeln(query(head,tail));14 end;15 end.
init即预处理过程，m为询问的组数。不断读入[head,tail]的待查询区间，给出查询值。
预处理就可以写出来：
1 procedure init; 2 var 3 i:longint; 4 begin 5 read(n); 6 for i:=1 to n do 7 read(a[i]); 8 tableLength:=trunc(ln(n)/ln(2)); 9 createTable(tableLength);10 make;11 end;
行5-行7就是总区间的读入。之后要打一个2的幂表用以拆分（运用倍增），打出了这个表才可以分区间——例子中的64就是这么算出来的。显然这个表长（也就是最大次数）=logL，写在代码中用换底公式后向下取整，得到表长。
之后以表长建立2的幂表，完成后进入预处理的核心部分make。
建表的code比较简单，不多加赘述。
1 procedure createTable(k:longint);2 var3 i:longint;4 begin5 powerTable[0]:=1;6 powerTable[1]:=2;7 for i:=2 to k do8 powerTable[i]:=2*powerTable[i-1];9 end;
预处理核心代码如下：
1 procedure make; 2 var 3 i,j:longint; 4 begin 5 for i:=1 to n do 6 line[i,0]:=a[i]; 7 for i:=1 to tableLength do 8 for j:=1 to n-powerTable[i]+1 do 9 line[j,i]:=max(line[j,i-1],line[j+powerTable[i-1],i-1]);10 end;
思想是DP的思想。对于总区间，先两端两端的划分，求其最值；再四段四段分，再八段八段分……line[i,j]表示序列中以i为起点，2的j次为长度的区间的最值。当j==0时自然就退化为当前位置的值。
要注意的是外层循环一定要是次数而不是起点，关于这点可以手动模拟一下感受感受；当外层循环为起点时，line数组求值中的依赖的有半段还未求出，故出错。
查询就比较简单了，由于预处理已经算出了所以可能用到的区间最值，只要做一次拆分，取两分区的max即可。
1 function query(left,right:longint):longint;2 var3 t:longint;4 begin5 t:=trunc(ln(right-left+1)/ln(2));6 exit(max(line[left,t],line[right-powerTable[t]+1,t]));7 end;
完整代码如下（其实只是多了点定义和一个max函数）：
1 var 2 a:array[0..100005]of longint; 3 i,n,m,head,tail,tableLength,temp:longint; 4 line:array[0..100005,0..17]of longint; 5 powerTable:array[0..17]of longint; 6 7 function max(a,b:longint):longint; 8 begin 9 if a>b then10 exit(a)11 else12 exit(b);13 end;14 15 procedure createTable(k:longint);16 var17 i:longint;18 begin19 powerTable[0]:=1;20 powerTable[1]:=2;21 for i:=2 to k do22 powerTable[i]:=2*powerTable[i-1];23 end;24 25 procedure make;26 var27 i,j:longint;28 begin29 for i:=1 to n do30 line[i,0]:=a[i];31 for i:=1 to tableLength do32 for j:=1 to n-powerTable[i]+1 do33 line[j,i]:=max(line[j,i-1],line[j+powerTable[i-1],i-1]);34 end;35 36 procedure init;37 var38 i:longint;39 begin40 read(n);41 for i:=1 to n do42 read(a[i]);43 tableLength:=trunc(ln(n)/ln(2));44 createTable(tableLength);45 make;46 end;47 48 function query(left,right:longint):longint;49 var50 t:longint;51 begin52 t:=trunc(ln(right-left+1)/ln(2));53 exit(max(line[left,t],line[right-powerTable[t]+1,t]));54 end;55 56 begin57 init;58 readln(m);59 for i:=1 to m do60 begin61 readln(head,tail);62 if head>tail then63 begin64 temp:=head;65 head:=tail;66 tail:=temp;67 end;68 writeln(query(head,tail));69 end;70 end.
行32的循环上界要控制好，否则会段出错，切记切记。
但是仅仅是ST是不够的。如
此题数据规模在m≤n≤2000000内，虽然按理来说不可能但是ST方法会超时。即是加了快读快输也不行。。。
ST超时代码示例：
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int powerTable[22],line[2000002][22],a[2000002],n,m; 8 9 void createTable(int size){10 powerTable[0] = 1;11 for (int i = 1; i <= size; ++i){12 powerTable[i] = 2 * powerTable[i-1];13 }14 }15 16 void init(){17 for (int i = 1; i <= n; ++i){18 line[i][0] = a[i];19 }20 for (int i = 1; i <= floor(log(n)/log(2)); ++i){21 for (int j = 1; j <= n-powerTable[i]+1; ++j){22 line[j][i] = min(line[j][i-1],line[j+powerTable[i-1]][i-1]);23 }24 }25 }26 27 int query(int head,int tail){28 int c = floor(log(tail-head+1)/log(2));29 return min(line[head][c],line[tail-powerTable[c]+1][c]);30 }31 32 int main(int argc, char const *argv[]){33 ios::sync_with_stdio(false);34 cin >> n >> m;35 for (int i = 1; i <= n; ++i){36 cin >> a[i];37 }38 cout << 0 << endl;39 createTable(floor(log(n)/log(2)));40 init();41 for (int i = 2; i <= n; ++i){42 if (i-m<=0){43 cout << query(1,i-1) << endl;44 }else{45 cout << query(i-m,i-1) << endl;46 }47 }48 return 0;49 }
快读快输部分：
1 void read(int &x){ 2 x=0;char c=getchar(); 3 while(c<'0' || c>'9')c=getchar(); 4 while(c>='0' && c<='9'){ 5 x=x*10+c-'0'; 6 c=getchar(); 7 } 8 } 9 10 void writeln(int x){11 int y=10,len=1;12 while(y<=x) {y*=10;len++;}13 while(len--){y/=10;putchar(x/y+48);x%=y;}14 putchar('\n');15 } 看来是没救了，试试线段树行不行。。。PS：题解显示是单调队列什么的，没仔细看。
Update：2018 - 06 - 06
找到st的模板题了：https://www.luogu.org/problemnew/show/P3865
用上面的代码改一下就好了，神奇的是cin/cout会超时7个点，改快读快写就A了。。
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int powerTable[22],line[2000002][22],a[2000002],n,m; 8 9 inline int read(){ 10 int s=0,w=1; 11 char ch=getchar(); 12 while(ch<='0'||ch>'9'){ if(ch=='-')w=-1;ch=getchar();} 13 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); 14 return s*w; 15 }16 17 inline void write(int x) { 18 if(x<0) putchar('-'),x=-x; 19 if(x>9) write(x/10); 20 putchar(x%10+'0'); 21 } 22 23 void createTable(int size){24 powerTable[0] = 1;25 for (int i = 1; i <= size; ++i){26 powerTable[i] = 2 * powerTable[i-1];27 }28 }29 30 void init(){31 for (int i = 1; i <= n; ++i){32 line[i][0] = a[i];33 }34 for (int i = 1; i <= floor(log(n)/log(2)); ++i){35 for (int j = 1; j <= n-powerTable[i]+1; ++j){36 line[j][i] = max(line[j][i-1],line[j+powerTable[i-1]][i-1]);37 }38 }39 }40 41 int query(int head,int tail){42 int c = floor(log(tail-head+1)/log(2));43 return max(line[head][c],line[tail-powerTable[c]+1][c]);44 }45 46 int main(int argc, char const *argv[]){47 n = read();48 m = read();49 for (int i = 1; i <= n; ++i){50 a[i] = read();51 }52 createTable(floor(log(n)/log(2)));53 init();54 for(int i = 1;i <= m;i++){55 int a = read(), b = read();56 write(query(a, b));printf("\n");57 }58 return 0;59 }