#include<iostream>
#include<stdio.h>
using namespace std;
const int maxa=200005;
int val[maxa];
struct tree{int max, left, right;
}tree[maxa*3];
int create(int root,int left,int right) //root的*2和*2+1分別存root的前后部分
{
tree[root].left=left;
tree[root].right=right;
if(left==right)
return tree[root].max=val[left];
int a,b,mid=(left+right)/2;
a=create(root*2,left,mid);
b=create(root*2+1,mid+1,right);
return tree[root].max=max(a,b);
}
int change(int root,int pos,int vall) //當(dāng)root代表的是改變的點時直接改變tree[root].max,其他與建樹部分相同
{
if(pos<tree[root].left||tree[root].right<pos)
return tree[root].max;
if(pos==tree[root].right&&pos==tree[root].left)
return tree[root].max=vall;
int a,b;
a=change(root*2,pos,vall);
b=change(root*2+1,pos,vall);
return tree[root].max=max(a,b);
}
int query(int root,int left,int right)
{
if(tree[root].left>right||tree[root].right<left) //root范圍與查詢范圍沒有任何交集時return 0；
return 0;
if(tree[root].left>=left&&tree[root].right<=right) //root范圍完全在查詢范圍時return tree[root].max;
return tree[root].max;
int a,b; //其他與建樹部分相同
a=query(root*2,left,right);
b=query(root*2+1,left,right);
return max(a,b);
}
int main()
{
//freopen("input.cpp","r",stdin);
int n,m;
char a;
int x,y;
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
}
create(1,1,n);
while(m--)
{
scanf("\n%c",&a);
scanf("%d%d",&x,&y);
if(a=='Q')
{
printf("%d\n",query(1,x,y));
}
else
change(1,x,y);
}
}
}

轉(zhuǎn)載于:https://www.cnblogs.com/icodefive/p/3599177.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。