st算法

算法"/>

st算法

st算法中的动态规划还不是完全理解，但是，就是因为这两个代码：

以下的文字：百度百科也讲的挺不错的
首先是预处理，用一个DP解决。设a[i]是要求区间最值的数列，f[i,j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样，Dp的状态、初值都已经有了，剩下的就是状态转移方程。我们把f[i，j]平均分成两段（因为f[i，j]一定是偶数个数字），从i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1为一段(长度都为2^（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。f[i，j]就是这两段的最大值中的最大值。于是我们得到了动规方程
F[i,j]=max（F[i，j-1],F[i+2^(j-i)，j-1]）.

void rmq_isit(bool ok)  
{  for(int i=1;i<=n;i++)  mm[i][0]=mi[i][0]=a[i];  for(int j=1;(1<<j)<=n;j++)  {  for(int i=1;i+(1<<j)-1<=n;i++)  {  if(ok)  mm[i][j]=max(mm[i][j-1],mm[i+(1<<(j-1))][j-1]);  else  mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);  }  }  
}  

如果不是全部二分，也不用怕，最后在来一次比较，即求交叉部分。
那么查询的时候对于任意一个区间 l – r ，我们同样可以得到区间差值 len = （r - l + 1）。
那么我们这一用小于2^k<=len，的 k 把区间分成可以交叉的两部分l 到 l+2^（k）- 1, 到 r -(1<

int rmq(int l,int r)  
{  int k=0;  while((1<<(k+1))<=r-l+1)  k++;  //printf("%d %d %d %d\n",l,l+(1<<k),r-(1<<k)+1,r-(1<<k)+1+(1<<k));  int ans1=max(mm[l][k],mm[r-(1<<k)+1][k]);  //交叉部分int ans2=min(mi[l][k],mi[r-(1<<k)+1][k]);  return ans1-ans2;  
}