151
【轉】POJ 3264 線段樹解法
每個算法都是數學家或者計算機學家多年研究的結果，不是我自己臆造的，所以學習一個新算法的最佳方法還是看寫的好的代碼。
按照慣例，我就粘貼一個網上寫的很好的帖子。。。
原文地址：https://ip96cns.blog.163.com/blog/static/17009519220112525029459/
線段樹的查找：（感謝高手指點，雖然隻是一點卻讓我把線段樹的內容理順了）這裏是我的一些總結吧
一個線段樹的結點表示一個區間，同時結點中保存所需要的信息。
如果詢問區間正好為這個線段樹的區間（左邊界和右邊界都相同），則返回該結點中保存的信息。
否則，遞歸往下查詢該結點的子結點（之後再返回的值就是子結點的值了，與當前結點無關了）
一直到“元線段”-不可再分之線段。
線段樹的結點的區間包含所有子結點的區間，並且子結點隻有兩個，同時子結點區間為父結點的一半，（二叉樹）
往下查詢的時候判斷詢問區間是否與當前結點表示區間的左右區間覆蓋，有三種情況
1，查詢區間在該結點表示區間中點右邊，此時隻需要往右孩子查詢
2.查詢區間在該結點表示區間中點左邊，此時隻需要往左孩子查詢
3.查詢區間包含該結點中點，這個時候要把查詢區間一分為2，即查詢區間的左邊界到中點，往左孩子查詢，以及中點到查詢區間的右邊界，往右孩子查詢。
這裏線段樹我用了兩種實現方式，不過在漸進複雜度上差別不大。當然這題目RMQ才夠快的。
我傳了兩個引用進去分別用來返回最大最小值。。。
第一種方法：
.從1~n區間建立靜態樹，然後先給區間[i,i](就是左右邊界相等的區間)賦值，然後再寫個函數求其他區間。
第二種方法：
從1~n區間建立靜態樹，並且將其中最大最小值構造為極小和極大，接著對於每個輸入數據，不斷的包含該數據所屬區間的最大最小值.比如說某個數據i在區間[l,r]中，修改這個區間的結點，然後再遞歸下去修改這個結點的子結點的區間.
（這樣就不需要為輸入數據的開辟一個數組，但是效果似乎似乎不太好。）
#include <iostream>
#include <stdio.h>
using namespace std;
struct node
{
int l,r;
int minvalue,maxvalue;
};
node nodes[10000000];
//
int cowheight[50010];
//
void queryinterval(int l,int r,int nodeindex,int& maxval,int& minval)
{
if(nodes[nodeindex].l==l&&nodes[nodeindex].r==r)
{
maxval=nodes[nodeindex].maxvalue;
minval=nodes[nodeindex].minvalue;
return ;
}
if(l==r)
{
maxval=minval=cowheight[l];
return ;
}
//
int mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2;
// 這個地方調試了很久才發現。。。如果這裏不錯就節省半天了
// mid=(l+r)/2 是錯的，必須是mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2
if(l>mid) queryinterval(l,r,nodeindex*2+2,maxval,minval);
else if(r<=mid) queryinterval(l,r,nodeindex*2+1,maxval,minval);
else
{
int max1,min1,max2,min2;
queryinterval(l,mid,nodeindex*2+1,max1,min1);
queryinterval(mid+1,r,nodeindex*2+2,max2,min2);
maxval=max1>max2?max1:max2;
minval=min1<min2?min1:min2;
return ;
}
}
//
//
void creattree(int l,int r,int index)
{
nodes[index].l=l;
nodes[index].r=r;
if(l==r)
{
nodes[index].maxvalue=nodes[index].minvalue=cowheight[l];
return;
}
creattree(l,(l+r)/2,index*2+1);
creattree((l+r)/2+1,r,index*2+2);
}
void addvalue(int index,int& maxval,int& minval)
{
if(nodes[index].l==nodes[index].r)
{
minval=maxval=nodes[index].maxvalue;
return ;
}
int max1,min1,max2,min2;
addvalue(index*2+1,max1,min1);
addvalue(index*2+2,max2,min2);
nodes[index].maxvalue=max1>max2?max1:max2;
nodes[index].minvalue=min1<min2?min1:min2;
maxval=nodes[index].maxvalue;
minval=nodes[index].minvalue;
return ;
}
//
int main()
{
int n,q;
scanf("%d%d",&n,&q);
//
int i;
for(i=1;i<=n;i++)
scanf("%d",&cowheight[i]);
//建樹
creattree(1,n,0);
int l,u;
addvalue(0,l,u);
//
for(i=0;i<q;i++)
{
int a,b;
scanf("%d%d",&a,&b);
int maxval,minval;
queryinterval(a,b,0,maxval,minval);
printf("%d\n",maxval-minval);
}
return 0;
}
#include <iostream>
#include <stdio.h>
using namespace std;
struct node
{
int l,r;
int minvalue,maxvalue;
node(){maxvalue=0; minvalue=0x7fffffff; }
}; node nodes[131072];
//
//
void queryinterval(int l,int r,int nodeindex,int& maxval,int& minval)
{
if(nodes[nodeindex].l==l&&nodes[nodeindex].r==r)
{
maxval=nodes[nodeindex].maxvalue;
minval=nodes[nodeindex].minvalue;
return ;
}
//
int mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2;
if(l>mid) queryinterval(l,r,nodeindex*2+2,maxval,minval);
else if(r<=mid) queryinterval(l,r,nodeindex*2+1,maxval,minval);
else
{
int max1,min1,max2,min2;
queryinterval(l,mid,nodeindex*2+1,max1,min1);
queryinterval(mid+1,r,nodeindex*2+2,max2,min2);
maxval=max1>max2?max1:max2;
minval=min1<min2?min1:min2;
return ;
}
}
//
//
void creattree(int l,int r,int index)
{
nodes[index].l=l;
nodes[index].r=r;
if(l<r)
{
creattree(l,(l+r)/2,index*2+1);
creattree((l+r)/2+1,r,index*2+2);
}
}
void addvalue(int pos,int val,int nodeindex)
{
if(nodes[nodeindex].l==nodes[nodeindex].r)
{
nodes[nodeindex].maxvalue=nodes[nodeindex].minvalue=val;
return ;
}
//
if(nodes[nodeindex].maxvalue<val) nodes[nodeindex].maxvalue=val;
if(nodes[nodeindex].minvalue>val) nodes[nodeindex].minvalue=val;
//
int mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2;
if(pos<=mid) addvalue(pos,val,nodeindex*2+1);
else addvalue(pos,val,nodeindex*2+2);
}
//
int main()
{
int n,q;
scanf("%d%d",&n,&q);
//
creattree(1,n,0);
int i,cowheight;
for(i=1;i<=n;i++)
{
scanf("%d",&cowheight);
addvalue(i,cowheight,0);
}
//
for(i=0;i<q;i++)
{
int a,b;
scanf("%d%d",&a,&b);
int maxval,minval;
queryinterval(a,b,0,maxval,minval);
printf("%d\n",maxval-minval);
}
return 0;
}
最後更新：2017-04-03 05:39:36