rmq(区间最值,不适用于要修改的情况)

(Range Minimum Query)
具体看代码,自己也不是很懂里面部分操作运算.
(要修改的情况就用线段树或树状数组)

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
const int maxn=1e5+5;
int n;
int max1[maxn][50];
int min1[maxn][50];
int a[maxn];

void yuchuli()
{
    for(int j=1;(1<<j)<=n;j++){
      for(int i=0;i+(1<<j)<n+1;i++){           //代表1左移j-1个位置,即2的j-1次方.
        max1[i][j]=max(max1[i][j-1],max1[i+(1<<(j-1))][j-1]);
        min1[i][j]=min(min1[i][j-1],min1[i+(1<<(j-1))][j-1]);
      }
    }
}

int rmq(int u,int v)
{
    int k = (int)(log(v-u+1.0)/log(2.0));//这一步好像也可以由其他方法.
    int a1= max(max1[u][k],max1[v-(1<<k)+1][k]);
    int a2= min(min1[u][k],min1[v-(1<<k)+1][k]);
    printf("%d\n",a1-a2);
}

int main()
{
    int m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++){
           scanf("%d",&a[i]);
           max1[i][0]=min1[i][0]=a[i];
        }
        yuchuli();
        while(m--)
        {   int u,v;
            scanf("%d%d",&u,&v);
            rmq(u-1,v-1);//求出该区间中的最大值与最小值的差.
        }
    }
}