线段树的简单题，纯粹是为了刷题
线段树的更新和查询
#include<iostream> using namespace std; #define N 200005 struct node { int l,r,m; }; node st[N*4]; int sou[N]; int mymax(int a,int b) { return a>b?a:b; } void build(int l,int r,int i) { st[i].l=l,st[i].r=r; if(l==r) { st[i].m=sou[l]; return ; } int mid=(l+r)/2; build(l,mid,i*2); build(mid+1,r,i*2+1); st[i].m=mymax(st[i*2].m,st[2*i+1].m); return ; } int query(int l,int r,int i) { if(st[i].l>=l&&st[i].r<=r) return st[i].m; int mid=(st[i].l+st[i].r)/2; if(l>mid) query(l,r,2*i+1); else if(r<=mid) query(l,r,2*i); else return mymax(query(l,mid,2*i),query(mid+1,r,2*i+1)); } void insert(int a,int b,int i) { if(st[i].l==st[i].r) { st[i].m=b; return ; } int mid=(st[i].l+st[i].r)/2; if(a<=mid) insert(a,b,2*i); else insert(a,b,2*i+1); st[i].m=mymax(st[i*2].m,st[i*2+1].m); return ; } int main() { int n,m,i,a,b; char chr; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) scanf("%d",sou+i); getchar(); build(1,n,1); for(i=1;i<=m;i++) { scanf("%c%d%d",&chr,&a,&b); getchar(); if(chr=='U') insert(a,b,1); if(chr=='Q') printf("%d/n",query(a,b,1)); } } return 0; }
