题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754
直接上代码和解释吧
1 #include<iostream> 2 #include<cstdio> 3 #define maxn 200000 4 int a[maxn],tree[maxn<<2]; 5 using namespace std; 6 7 int max(int x,int y) 8 { 9 return x>y?x:y; 10 } 11 12 void pushup(int now)//更新下一层两支点最大值 13 { 14 tree[now]=max(tree[now<<1],tree[now<<1|1]); 15 } 16 17 void build(int left,int right,int now)//构造数函数 18 { 19 if(left==right) 20 { 21 tree[now]=a[left]; 22 return; 23 }//赋值最底下一层数； 24 int mid=(left+right)>>1; 25 build(left,mid,now<<1); 26 build(mid+1,right,now<<1|1); 27 pushup(now);//赋值最底下以上的数； 28 } 29 30 void update(int a,int b,int left,int right,int now)//更新节点信息 31 { 32 if(right==a&&left==a) 33 { 34 tree[now]=b; 35 return; 36 }//跟新起始点值 ； 37 int mid=(left+right)>>1; 38 if(a<=mid) update(a,b,left,mid,now<<1); 39 else update(a,b,mid+1,right,now<<1|1); 40 pushup(now);// 更新起始点以上有关的支点信息； 41 } 42 43 int require(int L,int R,int left,int right,int now)//访问区间 ,L，R为给定的区间，另两个为正在访问的区间 44 { 45 if(left>=L&&right<=R) 46 { 47 return tree[now]; 48 }//如果现在访问的区间在我们要找的区间里面，就返回这个区间的最大数节点 49 int mid=(left+right)>>1,ans=-1; 50 if(L<=mid) 51 ans=max(require(L,R,left,mid,now<<1),ans);//访问左半边 ； 52 if(mid<R)//两个if，两边都要考虑； 53 ans=max(require(L,R,mid+1,right,now<<1|1),ans);//访问右半边，很巧。此处max里的ans为左半边的最大； 54 return ans;//所以直接返回ans值； 55 }
接下来是对访问的解释（不记下来怕自己忘了）：
/*
假设现有1 2 3 4 5 6 7 8 9 10 11 12数组
现在要访问2-4
第一步递归:因为1-12不在2-4里面，所以分为1-6和7-12两段，
而因为6大于4；故7-12不会访问，若访问的为2-7则会，这也是右边判断里不用等号原因之一，我想用也行吧，但假如访问2-6时6就会被算两次；
虽然最后不会影响判断最大值；
第二次递归：中点为3,故1-6又被分为1-3,4-6；目前没有哪一段可以返回值；
第三次递归： 分为4段：1-2；3-3；4-5；6-6；3-3（3-3在区间里）有返回值，并接下来的递归无6-6；
第四次递归：（完全分段）1-1；2-2；4-4；5-5；（2-2；4-4）有返回值；
结束递归，返回最大值；
*/
继续代码：
1 void mian(char str,int a,int b,int m) 2 { 3 if(str=='Q') 4 { 5 printf("%d ",require(a,b,1,m,1)); 6 return; 7 } 8 update(a,b,1,m,1); 9 } 10 11 int main() 12 { 13 int m,n; 14 while(~scanf("%d %d",&m,&n)) 15 { 16 char str; 17 int x,y; 18 for(int i=1;i<=m;i++) 19 scanf("%d",&a[i]); 20 build(1,m,1); 21 getchar(); 22 while(n--) 23 { 24 scanf("%c%d%d",&str,&x,&y); 25 mian(str,x,y,m); 26 getchar(); 27 } 28 } 29 return 0; 30 }
另外一个很好的参考网站，写的很好，我得保存下来：https://blog.csdn.net/yitongjun/article/details/53193724
总的来说：线段树是牺牲空间腾出时间的一个算法，里面有很多好巧的东西，让我边学边觉得不可思议，主要数的分支只有两个，造成每个节点与上一个节点有一定关系，即tree[n]的两个支点一定是tree[2*n]和tree[2*n+1];例外，关于线段树的操作函数有好几个，建树，访问树，修改树等，以后要多练习一下，里面递归作用梳理清楚后码起来还是可以的。嗯，这次就这样。