POJ3264[線段樹]

就是說有一個序列長度為n，q次詢問，詢問區間内最大值與最小值的差

可以說是經典的線段樹闆子題。。

第一次寫線段樹，有些漏洞請大家及時提出.

線段樹大概就是将元素配置設定，蒟蒻國文不好，大家請看圖

【圖檔來源：百度百科‘線段樹’】

大概是這個樣子，可以将時間複雜度壓縮到O（nlogn）【特别快對不對】

點這裡這裡A題

代碼這裡↓

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;


const int MAXV=50100;


struct Node
{
int mid;
int min;
int max;
int left;
int right;
}a[600100];


int h[MAXV],n,q,ansmin,ansmax;


void maketree(int x)
{
if(a[x].min==0&&a[x].max==0)
{
a[x].min=10000000;
a[x].max=-1;
}

if(a[x].left==a[x].right)
{
a[x].min=h[a[x].left];
a[x].max=h[a[x].left];
return;
}

a[x].mid=(a[x].left+a[x].right)/2;
a[2*x].left=a[x].left;
a[2*x].right=a[x].mid;
maketree(2*x);
a[2*x+1].left=a[x].mid+1;
a[2*x+1].right=a[x].right;
maketree(2*x+1);

a[x].min=min(a[2*x].min,a[2*x+1].min);
a[x].max=max(a[2*x].max,a[2*x+1].max);
}


void dfs(int l,int r,int x)
{

if(l==a[x].left&&r==a[x].right)
{
ansmin=min(ansmin,a[x].min);
ansmax=max(ansmax,a[x].max);
return;
}
if(l<=a[2*x].right)
{
if(r<=a[2*x].right)
{
dfs(l,r,2*x);
}
else
{
dfs(l,a[2*x].right,2*x);
dfs(a[2*x+1].left,r,2*x+1);
}
}
else
{
dfs(l,r,2*x+1);
}
}


int main()
{
int i,j,k,w,s,x,d,l,r;

scanf("%d%d",&n,&q);

for(i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}

a[1].left=1;
a[1].right=n;
maketree(1);

for(i=0;i<q;i++)
{
scanf("%d%d",&l,&r);
ansmin=100000000;
ansmax=-1;
dfs(l,r,0);

printf("%d\n",ansmax-ansmin);
}
return 0;
}