【Algorithm】区间最值 (RMQ)_St算法

ST算法的实现(最大值）：
首先是预处理，用一个DP解决。

设a[i]是要求区间最值的数列，F[i,j]表示从第i个数起连续2^j个数中的最大值。

F[1,0]表示第1个数起，长度为2^0=1的最大值，而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。

于是我们得到了动规方程F[i,j]=max{F[i，j-1],F[i+2^j-1，j-1]}.

预处理就是这样，接下来是得出最值，存在O(1)的方法。

还是分开来，把区间[l,r]分成两个长度为2^k的区间（保证有F[i,j]对应）。

  1: k:=trunc(ln(r-l+1)/ln(2))；
  2: ans:=max(F[l,k],F[r-1<<k+1，k])；

【Code】

  1: Program Poj2452(input,output);
  2:   var F:array[1..50000,0..16]of longint;
  3:       a:array[1..50001]of longint;
  4:       i,j,k,t,x,y,n,m:longint;
  5:   Function max(a,b:longint):longint;
  6:     begin if a>b then exit(a) else exit(b);end;
  7:   Function Ask(x,y:longint):longint;
  8:     begin
  9:       if x=y then exit(a[x])
 10:       else
 11:         begin
 12:           k:=trunc(ln(y-x+1)/ln(2));
 13:           exit(max(F[y-1<<k+1,k],F[x,k]));
 14:         end;
 15:     end;
 16:   begin
 17:     readln(n);
 18:     for i:=1 to n do read(a[i]);
 19:     for i:=1 to n do  F[i,0]:=a[i];
 20:     t:=trunc(ln(n)/ln(2));
 21:     for j:=1 to t do
 22:       for i:=1 to n do
 23:         if i-1<=n then
 24:           F[i,j]:=max(F[i,j-1],F[i+1<<(j-1),j-1])
 25:         else break;
 26:     readln(m);
 27:     for i:=1 to m do
 28:       begin
 29:         readln(x,y);
 30:         writeln(Ask(x,y));
 31:       end;
 32:   end.