【線段樹】hdu 1754 I hate it

最最基礎的線段樹,隻更新葉子節點,然後把資訊用PushUP(int r)這個函數更新上來

線段樹功能:update:單點替換 query:區間最值

#include<iostream>
#include<algorithm>
using namespace std;
int maxn[4000001],d[4000001];

void pushup(int rt)
{
	maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);
}

void build(int l,int r,int rt)
{
	if (l==r)
	{
		cin>>maxn[rt];
		return ;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,(rt<<1)+1);
	pushup(rt);
}

 void update(int p,int sc,int l,int r,int rt)
{
	if(l==r)
	{
		maxn[rt]=sc;
		return;
	}
	int m=(l+r)>>1;
	if (p<=m) update(p,sc,l,m,rt<<1);
	else update(p,sc,m+1,r,rt<<1|1);
	pushup(rt);
}

int getmax(int L,int R,int l,int r,int rt)
{
	if (L<=l && r<=R)
	{
		return maxn[rt];
	}
	int m=(l+r)>>1;
	int ret=0;
	if(L<=m)ret=max(ret,getmax(L,R,l,m,rt<<1));
	if(R>m)ret=max(ret,getmax(L,R,m+1,r,(rt<<1)+1));
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	int n,m,a,b;
	char ch;
	while (cin>>n>>m)
	{
		build(1,n,1);
		for (int i=0;i<m;i++)
		 {
		 	cin>>ch>>a>>b;
		 	if (ch=='U') update(a,b,1,n,1);
		 	else cout<<getmax(a,b,1,n,1)<<endl;
		 }
	}
	return 0;
}