樹狀數組求區間極值(不帶修改)

衆所周知樹狀數組有着良好的特性：代碼短，效率高。

但這樣優良的資料結構不應隻用于我們最初知道的,最基本的應用：單點修改，查詢字首和。

其應用可以更為廣泛，如單點修改，查詢區間極值。

由于區間極值無法像求區間和一樣用兩個字首和之差來求，故其查詢操作應對應的進行修改。

先從樹狀數組如此優秀的根源說起吧。它之是以擁有O(nlogn)的單點查詢修改的複雜度，是因為它将1~n分為了至多logn塊，每次操作隻需對至多logn塊進行，而求字首和正是利用了這一點。而求區間極值可不可以也用分塊的思想來優化呢？當然。

如何利用樹狀數組已有的性質将l~r這一區間分塊呢？

如圖（侵删）：

如果要将4~9這一區間分塊的話，為了保證效率，會将其分為4,5~6,7,8,9這幾個區間。

顯然我們所分區間越大，其效率就越高。是以便采用了這一分法。

将其一般化就是說：如果max[r]所代表的區間超出了l~r這一區間，那麼隻能将其單獨分為一塊，

否則，就将[r-lowbit(r),r]分為一塊，以充分利用已知資訊。

代碼（poj 3264）如下：

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 60000

#define ll long long
using namespace std;
inline void read(int &x){
    char ch;
    bool flag=false;
    for (ch=getchar();!isdigit(ch);ch=getchar())if (ch=='-') flag=true;
    for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    x=flag?-x:x;
}
inline void write(int x){
    static const int maxlen=100;
    static char s[maxlen];
        if (x<0) {   putchar('-'); x=-x;}
    if(!x){ putchar('0'); return; }
    int len=0; for(;x;x/=10) s[len++]=x % 10+'0';
    for(int i=len-1;i>=0;--i) putchar(s[i]);
}

int n,m;
int a[maxn];
int Max[maxn],Min[maxn];

int lowbit(int x){
return x&(-x);
}


void insert(int x,int v){
while (x<=n){
		Max[x]=max(Max[x],v);	Min[x]=min(Min[x],v);
		x+=lowbit(x);
	}
}

int query(int l,int r){
int MAX=a[l],MIN=a[r];
while (1)
	{
		MAX=max(MAX,a[r]); MIN=min(MIN,a[r]);
		if (l==r)	break;
		for (r-=1;r-l>=lowbit(r);r-=lowbit(r))
			{
				MAX=max(Max[r],MAX);	MIN=min(Min[r],MIN);
			}
	}
//printf ("%d-----%d :  MAX=%d  MIN=%d\n",l,r,MAX,MIN);
return (MAX-MIN);
}



int main(){
read(n); read(m);
memset(Min,0x3f,sizeof(Min));
for (int i=1;i<=n;i++)
	read(a[i]);
for (int i=1;i<=n;i++)
	insert(i,a[i]);
for (int i=1;i<=m;i++)
	{
		int x,y;
		read(x); read(y);
		write(query(x,y));
		puts("");
	}
}