线段树单点更新模板 求区间最大值
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 using namespace std; int n,m,tre[800010]; void build(int num,int s,int e) { int a; if(s==e) { scanf("%d",&a); tre[num]=a; return ; } int mid=(s+e)>>1; build(num<<1,s,mid); build(num<<1|1,mid+1,e); tre[num]=max(tre[num<<1],tre[num<<1|1]); } void update(int num,int s,int e,int pos,int val) { if(s==e) { tre[num]=val; return ; } int mid=(s+e)>>1; if(pos<=mid) update(num<<1,s,mid,pos,val); else update(num<<1|1,mid+1,e,pos,val); tre[num]=max(tre[num<<1],tre[num<<1|1]); } int query(int num,int s,int e,int l,int r) { if(l<=s&&e<=r) { return tre[num]; } int mid=(s+e)>>1; if(r<=mid) return query(num<<1,s,mid,l,r); else if(l>mid) return query(num<<1|1,mid+1,e,l,r); else return max(query(num<<1,s,mid,l,mid),query(num<<1|1,mid+1,e,mid+1,r)); } int main() { int a,b; char str[10]; while(~scanf("%d%d",&n,&m)) { build(1,1,n); while(m--) { scanf("%s",&str); if(str[0]=='U') { scanf("%d%d",&a,&b); update(1,1,n,a,b); } else { scanf("%d%d",&a,&b); printf("%d\n",query(1,1,n,a,b)); } } } return 0; }