題目：HDU1754

#include <stdio.h> #define maxn 222222#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1int MAX[maxn<<2];int max(int a,int b) {return a>b? a:b; }void PushUP(int rt) {MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]); }void Build(int l,int r,int rt) {if(l==r){scanf("%d",&MAX[rt]);return;}int m=(l+r)>>1;Build(lson);Build(rson);PushUP(rt); }void Update(int p,int add,int l,int r,int rt) {if(l==r){MAX[rt]=add;return;}int m=(l+r)>>1;if(p<=m)Update(p,add,lson);elseUpdate(p,add,rson);PushUP(rt); }int Query(int L,int R,int l,int r,int rt) {if(L<=l&&R>=r)return MAX[rt];int m=(l+r)>>1;int ret=0;if(L<=m) ret=max(ret,Query(L,R,lson));if(R>m) ret=max(ret,Query(L,R,rson));return ret; }int main() {int N,M;char s[5];while(~scanf("%d%d",&N,&M)){Build(1,N,1);while(M--){int a,b;scanf("%s%d%d",s,&a,&b);if(s[0]=='Q')printf("%d\n",Query(a,b,1,N,1));elseUpdate(a,b,1,N,1);}}return 0; }

?

總結

以上是生活随笔為你收集整理的线段树求区间最大值RMQ(单点更新)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。