ST算法（Sparse Table，稀疏表）

本文主要是介绍ST算法（Sparse Table，稀疏表），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【ST算法描述】

信息学竞赛中，经常会出现RMQ问题，即求区间最大（小）值问题。那么，我们该如何求解呢？ST算法横空出世。 

ST算法（Sparse Table，稀疏表）主要用于解决区间最值问题（即RMQ问题）。因为ST算法求解RMQ问题时的时间复杂度只有O(nlogn)，查询时间复杂度为常数阶O(1)，所以我们还常称ST算法为TLE（Time Limit Exceeded）的死敌。虽然还可以使用线段树、树状数组、splay等算法求解区间最值问题，但是ST算法比它们更快，更适用于在线查询。

ST算法分成两部分：
离线预处理O(nlogn)和在线查询O(1)。

（1）离线预处理：运用DP思想求解区间最值，并将结果保存到一个二维数组中。

（2）在线查询：对给定区间进行分割，并借助上步中的二维数组求最值

具体解释：

（1）离线预处理

ST算法使用DP思想求解区间最值，貌似属于区间动态规划。不过区间在增加时，每次并不是增加一个长度，而是使用倍增的思想，每次增加2^i个长度。
 

使用F[i,j]表示以i为起点，区间长度为2^j的区间最大（小）值，此时对应的区间为[i,i+2^j-1]，区间长度为2^j。

例如，给出一数组A[0~5]={5,4,6,10,1,12},则F[0,2]表示区间[0,3]的最小值，等于4。F[2,2]表示区间[2,5]的最小值，等于1。

在求解F[i,j]时，ST算法先将长度为2^j的区间[i,i+2^j-1]分成[i,i+2^(j-1)-1]及[i+2^(j-1),i+2^(j-1)+2^(j-1)-1]两等份，分别对应于F[i,j-1]和F[i+2^(j-1),j-1]。显然，每份区间长度均为2^(j-1)。
 

之后，再分别求解这两个区间F[i,j-1]和F[i+2^(j-1),j-1]的最值。
最后，再结合这两个区间的最值，求出整个区间的最值。
特殊情况，当j=0时，F[i,j]=F[i,0]。此时，将j=0代入区间长度公式2^j，可得F[i,0]对应的区间长度等于1（2^j=2^0=1），即区间中只有一个元素。此时，F[i,0]分别等于初始输入的每一个元素的值。

例如，给出一数组A[0~5]={5,4,6,10,1,12}，要求解F[1,2]的值，即求解区间[1,4]={4,6,10,1}的最小值，此时需要先把这个区间[1,4]分成两个等长的区间[1,2]、[3,4]（分别对应F[1,1]）、F[3,1]），之后再分别求解这两个区间的最小值。然后，依次规律迭代求解。

由上分析可得利用ST算法求解区间最小值问题的状态转移方程是： F[i,j]=min(F[i,j-1],F[i+2^(j-1),j-1])

初始状态为：F[i,0] = A[i]
 

（2）在线查询
在上文第（1）步的离线预处理阶段，每一个状态对应的区间长度都为2^i。但是，在本步所指的在线查询阶段，由于给出的待查询区间的长度不一定恰好为2^i，因此我们需要对查询区间进行处理。

处理原则是将给定的待查询区间分成满足如下条件的两个小区间：

• 两个小区间能覆盖整个区间
• 为了利用离线预处理阶段的结果，要求两个小区间长度相等且都为2^i（注意：两个小区间可能重叠）

其中，若待查询区间为[L,R]，则上步2^i中的i=int(log2(R-L+1)),即i等于对区间长度取以2为底的对数。
显然，根据上述思想，可以把待查询区间[L,R]分成两个小区间[L,L+2^i-1]和[R-2^i+1,R]，它们分别对应F[L,i]和F[R-2^i+1,i]。之后，为了求解给定区间[L,R]的最小值，我们只需求[L,L+2^i-1]和[R-2^i+1,R]这两个区间的最小值即可。此算法的时间复杂度是O(1)。
 

例如，若给定的待查询区间[L,R]为[3,11]，则分解为两个小区间的计算步骤为：

∵ L=3,R=11  ∴ i=int(log2(R-L+1))=int(log2(11-3+1))=3，2^i=2^3=8
则[L,R]分成的两个小区间分别为：
[L,L+2^i-1]=[3,3+8-1]=[3,10]
[R-2^i+1,R]=[11-8+1,11]=[4,11]
那么，query(L,R)=min(F[L,i],F[R-2^i+1,i])

这篇关于ST算法（Sparse Table，稀疏表）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！