初识线段树

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxx 200005
#define l(u) (u<<1)
#define r(u) (u<<1|1)
using namespace std;
int n,m,cj[200005],j,b,ans;
struct data{
	int l,r,sum;
}a[maxx<<2];
char c;
void build(int x,int l,int r)
{
	a[x].l=l;a[x].r=r;
	if(l==r)
	{
		a[x].sum=cj[l];
		return ;
	}
	int mid=(r+l)/2;
	build(l(x),l,mid);
	build(r(x),mid+1,r);
	a[x].sum=max(a[l(x)].sum,a[r(x)].sum);
}
void update(int x,int l,int r)
{
	if(a[x].l==a[x].r)
	{
		a[x].sum=r;
		return ;
	}
	int mid=(a[x].r+a[x].l)/2;
	if(l<=mid)update(l(x),l,r);
	else update(r(x),l,r);
	a[x].sum=max(a[l(x)].sum,a[r(x)].sum);
}
int cz(int x,int l,int r)
{
	if(a[x].l==l&&a[x].r==r)
		return a[x].sum;
	int mid=(a[x].r+a[x].l)>>1;
	if(r<=mid) return cz(l(x),l,r);
	else if(l>=mid+1)return cz(r(x),l,r);
	else return max(cz(l(x),l,mid),cz(r(x),mid+1,r));
}
int main()
{
	freopen("e.in","r",stdin);
	freopen("e.out","w",stdout);
	while(scanf("%d%d",&n,&m)==2)
	{
		for (int i=1;i<=n;i++)
		scanf("%d",&cj[i]);
		build(1,1,n);
		for(int i=1;i<=m;i++)
		{
			cin>>c>>j>>b;
			if(c==‘Q‘)
			{
				int ans=cz(1,j,b);
				cout<<ans<<endl;
			}
			if(c==‘U‘)
			{
				update(1,j,b);
			}
		}
	}
	return 0;	
}

#include <stdio.h>
#define M 50005

struct data
{
    int l,r;
    int tall,shor;
}line[3*M];
int num[M];
int min (int a,int b)
{
    return a > b?b:a;
}
int max (int a,int b)
{
    return a > b?a:b;
}
int low,hei;
void BuildTree(int left,int right,int u)
{
    line[u].l = left;
    line[u].r = right;
    if (line[u].l == line[u].r)
    {
        line[u].tall = num[left];
        line[u].shor = num[left];
        return ;
    }
    int mid = (line[u].l+line[u].r)/2;
    BuildTree(left,mid,2*u);
    BuildTree(mid+1,right,2*u+1);
    line[u].tall = max (line[2*u].tall,line[2*u+1].tall);
    line[u].shor = min (line[2*u].shor,line[2*u+1].shor);
   
}
void query (int left,int right,int u)
{
    if (line[u].l == left&&line[u].r == right)
    {
        low = min (low,line[u].shor);
        hei = max (hei,line[u].tall);
        return ;
    }
    int mid = (line[u].l + line[u].r)/2;
    if (right <= mid)
        query (left,right,2*u);
    else if (left >= mid + 1)
        query (left,right,2*u+1);
    else
    {
        query(left,mid,2*u);
        query (mid+1,right,2*u+1);
    }
}
int main ()
{
    int n,m,a,b;
    scanf ("%d%d",&n,&m);
    for (int i = 1;i <= n;i ++)
        scanf ("%d",&num[i]);
    BuildTree(1,n,1);
    while (m --)
    {
        scanf ("%d%d",&a,&b);
        low = 1000001;
        hei = 0;
        query (a,b,1);
        printf ("%d\n",hei - low);
    }
    return 0;
}