-------------------------------------算法简述-----------------------------------------

ST算法O(nlogn)预处理,O(1)的查询指定区间的最值(以最小值为例)

基本上是把待求区间[l,r]分为两段长为len的区间

左边一段为[l,l+len-1],右边一段为[r-len+1,r]

len必须使得两段区间覆盖待求区间

设所求数组为w

那么,所求最小值就是两个区间的最小值间的最小值

即min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})

若都在预先处理中先求得两个区间的最小值

则每次查询的复杂度都是O(1)

---

对len做一个限制:只能为2的幂

在预处理中求出所有mi[b][t] : 以b为起点,长为2^t的区间的最小值.

则求解min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})

就变成min(mi[l][t],mi[r-2^t+1][r]),其中t可以由此得出,以保证两段区间可以覆盖待求区间:

t=ln(r-l+1)/ln(2)

---

可以看到mi[b][t]=min(mi[b][t-1],mi[b+2^(t-1)-1][t-1])

特别地对于所有mi[i][0],其值都是w[i];

由此自底向上推出所有的mi[b][t]

mi大小为n*logn,预处理时间复杂度为O(nlogn),查询时间复杂度为O(1)

-----------------------------------------------------代码------------------------------------------------------

在POJ上测试, 反应良好~

不知道怎么样把函数指针指向任意类型的<操作符, 只能总是提供一个"小于"函数

查询指定区间的最小值.

----------------------------------以下是模板-------------------------------------

template < class Type>
class rmq_st{
private:
      Type* body;   
      int** mi;      
      int size;     
      int len;     

      int dint(double a){       
          int buf=a;   
          if(buf>a){
              --buf;
          }
          return buf;
      }

      int mlen(int l,int r){
          double buf=log((double)(r-l+1))/log((double)2);  
          return dint(buf)
      }   
      bool (*less)(Type& t1,Type& t2);

public:

     //构造函数 : (待求数组,大小,小于函数)      
      rmq_st(Type* con,int s,bool (*lessthan)(Type& t1,Type& t2));
           
      ~rmq_st();//解构
     
      Type get_body(int p);//返回指定索引的元素

      int query_index(int l,int r);//返回指定区间最小值的元素索引

      Type query(int l,int r);//返回指定区间的最小元素
};

template < class Type>
rmq_st< Type>::rmq_st(Type* con,int s,bool (*lessthan)(Type& t1,Type& t2)){
      less=lessthan;
      body=con;
      size=s;
      len=mlen(0,s-1)+1;
      mi=new int*[size];
      int i,j;
      for(i=0;i< size;++i){
          mi[i]=new int[len];
      }
      int bound;  
      int a,b;    
      for(i=0;i< size;++i){   
          mi[i][0]=i;
      }
      for(i=1;i< len;++i){     
          bound=n-(1<< i)+1;      
          for(j=0;j< bound;++j){      
              a=mi[j][i-1];       
              b=mi[j+(1<< (i-1))][i-1];    
              mi[j][i]=less(body[a],body[b])?a:b;
          }
      }
}

template < class Type>
rmq_st< Type>::~rmq_st(){
      int i;
      for(i=0;i< size;++i){
          delete[] mi[i];
      }    
      delete[] mi;
}

template < class Type>
Type rmq_st< Type>::get_body(int p){
      return body[p];
}

template < class Type>
int rmq_st< Type>::query_index(int l,int r){
      int length=mlen(l,r);        
      int a=mi[l][length];
      int b=mi[r-(1<< length)+1][length];
      return less(body[a],body[b])?a:b;
}

template < class Type>
Type rmq_st< Type>::query(int l,int r){
      int length=mlen(l,r);
      int a=mi[l][length];
      int b=mi[r-(1<< length)+1][length];
      return less(body[a],body[b])?body[a]:body[b];
}

/*----------------Example : POJ 3264    Memory:7708K   Time:3230MS-----------------*/

int cow[50001];
int n,q;

bool cmpmin(int& t1,int& t2){
      return t1< t2;
}

bool cmpmax(int& t1,int& t2){
      return t1>t2;
}

int main()
{
//    freopen("1.in","r",stdin);
      scanf("%d %d",&n,&q);
      int i;    
      for(i=0;i< n;++i){
          scanf("%d",&cow[i]);
      }
      rmq_st< int> minst(cow,n,cmpmin);
      rmq_st< int> maxst(cow,n,cmpmax);
      int a,b;
      for(i=0;i< q;++i){
          scanf("%d %d",&a,&b);
          --a;
          --b;
          printf("%d\n",maxst.query(a,b)-minst.query(a,b));
      }      
      return 0;
}