提供原程序和具体分析如下：
提供原程序前，先进行如下几点说明（源程序的风格）：
•maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍
•lson和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示
•以前的写法是另外开两个个数组记录每个结点所表示的区间,其实这个区间不必保存,一边算一边传下去就行,只需要写函数的时候多两个参数,结合lson和rson的预定义可以很方便
•PushUP(int rt)是把当前结点的信息更新到父结点
•PushDown(int rt)是把当前结点的信息更新给儿子结点
•rt表示当前子树的根(root),也就是当前所在的结点
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 #define lson l , m , rt << 1 //用lson来代替三个参数：l,m,rt*2，注意rt<<1就是rt*2; 6 #define rson m + 1 , r , rt << 1 | 1 //同上，rt<<1|1，相当于rt*2+1; 7 const int maxn =222222; 8 int MAX[maxn<<2]; //二进行向右移两位相当于maxn*4; 9 void PushUP(int rt){ //用于向上回溯 10 MAX[rt]= max(MAX[rt<<1] , MAX[rt<<1|1]); //选择左右孩子中的较大者 11 } 12 void build(int l,int r,int rt){ //建立线段树 13 if(l == r){ 14 scanf("%d",&MAX[rt]); //至叶结点时读数 15 return; 16 } 17 int m =(l + r)>>1; 18 build(lson); //线段树分为左孩子 19 build(rson); //线段树分为右孩子 20 PushUP(rt); //向上回溯 21 } 22 void update(int p,int sc,int l,int r,int rt){ 23 if(l == r){ 24 MAX[rt]= sc; 25 return; 26 } 27 int m =(l + r)>>1; 28 if(p <= m) update(p , sc , lson); 29 else update(p , sc , rson); 30 PushUP(rt); 31 } 32 int query(int L,int R,int l,int r,int rt){ 33 if(L <= l && r <= R){ 34 return MAX[rt]; 35 } 36 int m =(l + r)>>1; 37 int ret =0; 38 if(L <= m) ret = max(ret , query(L , R , lson)); 39 if(R > m) ret = max(ret , query(L , R , rson)); 40 return ret; 41 } 42 int main(){ 43 int n , m; 44 while(~scanf("%d%d",&n,&m)){ 45 build(1 , n , 1); 46 while(m --){ 47 char op[2]; 48 int a , b; 49 scanf("%s%d%d",op,&a,&b); 50 if(op[0]==‘Q‘)printf("%d\n",query(a , b , 1 , n , 1)); 51 else update(a , b , 1 , n , 1); 52 } 53 } 54 return 0; 55 }
原文：http://www.cnblogs.com/jjzzx/p/5252649.html