st算法——RMQ的一个简单可行的算法

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。——百度百科

求出数组中任意区间[l,r]的最值，朴素的算法需要O(n)的时间。当询问特别多时，效率十分低。 st算法可以在O(nlogn)的时间内做完预处理，然后用O(1)的时间回答每一个问题。具体实现方法如下：（其实是一个动规^_^） 以求最大值为例。 用f[i,j]表示区间[i,i+2j-1]中的最大值。那么： f[i,j]=max(F[i,j-1],F[i+2j-1,j-1]) 预处理完后，对于询问求[a,b]的最大值。我们首先需要求出一个最大的整数x满足2x <=r-l+1那么，答案就是max(f[a,x],f[b+1-2x,x])。

由于pascal中，log2函数在math库中，使用还需uses math; 而ln则不需要使用任何的库，所以可以考虑换底公式： log a(b)=log c(b)/log c(a) 也就是log2(a)=ln(a)/ln(2)

例题如：Balanced Lineup,USACO 2007 January Silver（即PKU3264）。求区间的最大值-最小值。程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

{$inline on}
var n,q,x,y,i,j,k:longint;
    Fmin,Fmax:array[1..50000,0..30]of longint;
function min(a,b:longint):longint;inline;begin if(ab)then exit(a)else exit(b)end;
begin
  assign(input,'lineup.in');reset(input);
  assign(output,'lineup.out');rewrite(output);

  readln(n,q);
  for i:=1 to n do begin
    readln(Fmin[i,0]);
    Fmax[i,0]:=Fmin[i,0];
  end;
  for j:=1 to trunc(ln(n)/ln(2)) do
    for i:=1 to n+1-1 shl j do begin
      Fmin[i,j]:=min(Fmin[i,j-1],Fmin[i+1 shl (j-1),j-1]);
      Fmax[i,j]:=max(Fmax[i,j-1],Fmax[i+1 shl (j-1),j-1]);
    end;
  for i:=1 to q do begin
    readln(x,y);
    k:=trunc(ln(y-x+1)/ln(2));
    writeln(max(Fmax[x,k],Fmax[y+1-1 shl k,k])-min(Fmin[x,k],Fmin[y+1-1 shl k,k]));
  end;

  close(input);close(output);
end.

Comments