再次理解線段樹。比第一次又有了更深刻的認識，雖然還不能完全靠自己寫出來，但自己慢慢的去摸索，一定能慢慢理解那個套路了。加油，拿下線段樹。

同時，推薦北大郭煒講的線段樹。

poj3264

#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;
#define MY_MIN 99999999
#define MY_MAX -99999999
struct CNode{
int L,R;
int nMin,nMax;
CNode *pLeft,*pRight;
};

int min ( const int a, const int b ) {
return (b<a)?b:a;
}
int max ( const int a, const int b ) {
return (b<a)?a:b;
}


int nMax,nMin; //用于記錄最大值和最小值
CNode Tree[1000000]; //一般為葉子節點的兩倍
int nCount=0; //總節點數

void Build(CNode *pRoot,int L,int R){
//建線段樹

pRoot->L=L;pRoot->R=R;
pRoot->nMin=MY_MIN;pRoot->nMax=MY_MAX;
if(L!=R){
nCount++;
pRoot->pLeft=Tree+nCount;
nCount++;
pRoot->pRight=Tree+nCount;
Build(pRoot->pLeft,L,(L+R)/2);
Build(pRoot->pRight,(L+R)/2+1,R);
}
}

void Insert(CNode *pRoot,int i,int v){
//將第i個數（其值為v）插入到線段樹中
if(pRoot->L==i && pRoot->R==i){
pRoot->nMin=pRoot->nMax=v;
return;
}
pRoot->nMax=max(pRoot->nMax,v);
pRoot->nMin=min(pRoot->nMin,v);
if(i<=(pRoot->R+pRoot->L)/2){
Insert(pRoot->pLeft,i,v);
}
else{
Insert(pRoot->pRight,i,v);
}
}

void Query(CNode *pRoot,int L,int R){
if( pRoot->nMin>= nMin && pRoot->nMax <= nMax) //這沒理解到。哎。
return;
if(pRoot->L==L && pRoot->R==R)
{
nMax=max(pRoot->nMax,nMax); //這當時也沒注意到要用函數。
nMin=min(pRoot->nMin,nMin);
return;
}
else if(R<=(pRoot->R+pRoot->L)/2){
Query(pRoot->pLeft,L,R);
}
else if(L>=(pRoot->R+pRoot->L)/2+1){
Query(pRoot->pRight,L,R);
}
else{
Query(pRoot->pLeft,L,(pRoot->R+pRoot->L)/2);
Query(pRoot->pRight,(pRoot->R+pRoot->L)/2+1,R);
}
}

int main(){
int m,n,x,y;
int v,i;
scanf("%d %d",&m,&n);
Build(Tree,1,m);
for(i=1;i<=m;i++){
scanf("%d",&v);
Insert(Tree,i,v);
}
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
nMax = MY_MAX;
nMin = MY_MIN;
Query(Tree,x,y);
printf("%d\n",nMax-nMin);
}
return 0;
}

?

?

?

轉載于:https://www.cnblogs.com/Jason-Damon/archive/2012/02/21/2361937.html

總結

以上是生活随笔為你收集整理的poj3264 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。