前段时间做16年多校联合赛的Contest 1的D题（HDU 5726）时候遇到了多次查询指定区间的gcd值的问题，疑惑于用什么样的方式进行处理，最后上网查到了ST表，开始弄得晕头转向，后来才慢慢找到了一点门道，于是把这些东西都写下来，以备不时之需。
关于ST表：
首先需要特别说明，ST表的适用范围主要用于区间查询，因为如果要涉及更改的话需要改变整个ST表的值，在理论上，ST表建表的复杂度为O（nlogn），比线段树的单点更新的O（logn）还是要高一些的，面对大量修改操作的时候有超时风险，故不推荐在需要单点更新的更不用说区间更新题目中使用。
含义：那么在原理上，ST表中的某一点代表的的是原数据集中一段区间的特殊值，比如最大值，最小值，最大公约数等。以最大值为例，ST表中一点st[i][j]，代表数据集中标号为i到i+2^j-1的区间的最大值。
推导：使用递归公式：st[i][j] = max(st[i][j-1],st[i+2^(j-1)][j-1])可以计算出st表中各点的值，其原理是，将(i,i+2^j-1)这个区间分开成(i,i+2^(j-1)-1)和(i+2^(j-1),i+2^j-1)这两个区间，然后比较这两个区间哪个大，并将大的保留，即为st(i,j)的值，使用了动态规划和贪心的思想，将区间划分为多个小区间，之后再整合。
查询：ST表本质还是用来帮助我们快速查找区间的特殊知道，但是根据刚刚我们对ST的介绍，我们可以很快发现ST表中好像只存储了长度为2^j的区间的值，但是我们平时的查询中，区间长度肯定不可能都恰好等于2^j，那我们怎么去查询那些区间长度不为2^j的特殊值呢，其实方法很简单，就是切割这个区间。把这个区间分为两个长度为2^(j-1)的子区间（两个子区间可能会有重叠部分，但是不会对结果产生影响）。这样，我们对这两个子区间进行查询，之后求出从这两个子区间求出的最大值谁更大，就把哪个定为原区间的最大值就好了。因为2^(j-1)已经在st数组中存放好，所以可以得到快速的得到结果。因为一次查询只要读取数组中两个点的值，所以复杂度为O(1)。
下面给两个样题，希望能对大家有帮助：
第一个题是UESTC-1591（点击可以查看原题），题目要求求指定区间的最大值与最小值的差，原本是一个线段树的样题，但是看了ST表以后，感觉用ST表写起来会更方便一些，其中既包括了求最大值，也包括了求最小值，比较有代表性。下面是ST表写完的AC代码：
#include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> using namespace std; const int maxn=50005; int stmax[maxn][20]; int stmin[maxn][20]; int n,m; void ST() { int k=int(log(1.0*n)/log(2.0)); for(int j=1; j<=k; j++) { for(int i=1; i+(1<<j)-1<=n; i++) { stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]); stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]); } } } int qmax(int l,int r) { int k=int(log(1.0*(r-l+1))/log(2.0)); return max(stmax[l][k],stmax[r-(1<<k)+1][k]); } int qmin(int l,int r) { int k=int(log(1.0*(r-l+1))/log(2.0)); return min(stmin[l][k],stmin[r-(1<<k)+1][k]); } int main() { scanf("%d %d",&n,&m); for(int i=1; i<=n; i++) { int temp; scanf("%d",&temp); stmax[i][0]=stmin[i][0]=temp; } ST(); for(int i=0; i<m; i++) { int a,b; scanf("%d %d",&a,&b); int ans=qmax(a,b)-qmin(a,b); printf("%d ",ans); } return 0; }
之后的第二个样题是HDU 5726，是求一个区间的最大公约数，并且同时输出有多少个区间和这个区间的最大公约数相同。因为这个题目需要知道有多少个区间的最大公约数和那个区间相同，考虑到规模很明显不能现算，所以用ST表是一种不错的选择，这个题目同时还涉及到了gcd的不会递增的性质和二分查找，大家只需要关注一下ST表的建立和查询那部分就好了。
AC代码：
#include <stdio.h> #include <math.h> #include <map> #include <string.h> #include <iostream> using namespace std; const int maxn=100005; map<int,long long> mp; int gcd(int a,int b){ if(b==0){ return a; } return gcd(b,a%b); } int n,m; int st[maxn][25]; void ST(){ int k=int(log(1.0*n)/log(2.0)); for(int j=1;j<=k;j++){ for(int i=0;i+(1<<j)<=n;i++){ st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } } int query(int l,int r){ int k=int(log(1.0*(r-l+1))/log(2.0)); return gcd(st[r-(1<<k)+1][k],st[l][k]); } int main(){ int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++){ memset(st,0,sizeof(st)); mp.clear(); scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&st[i][0]); } ST(); for(int i=0;i<n;i++) { int t,ll=i; while(ll<n) { t=query(i,ll); int l=ll,r=n-1; while(l<r) { int mid=(l+r+1)>>1; if(query(i,mid)>=t)l=mid; else r=mid-1; } mp[t]+=l-ll+1; ll=l+1; } } int q; scanf("%d",&q); printf("Case #%d: ",cas); while(q--) { int l,r; scanf("%d%d",&l,&r); l--,r--; printf("%d %I64d ",query(l,r),mp[query(l,r)]); } } return 0; }