本文主要是介绍hdu 1754 (线段树)I Hate It，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个是我的第一道线段树。
总之，看过理解了二分搜索树的，基本上，看这个线段树，没什么难度的。
把一个区间分成左右两个儿子。左儿子比父亲区间的中点小，右二子大。
比如，[1,10]为父亲节点，那么左儿子节点为[1,5],右儿子为[6,10].
这样每个节点保存相应的数据。比如，此题保存为这段区间的最大分数。
总的时间为O(logN).
#include <iostream>
using namespace std;
int n,m;
int ts,te;
int mg;
int sgTree[530000]; //线段树的数组形式.i*2为左儿子节点，i*2+1为右儿子节点int max(int a,int b)
{return a>b?a:b;
}void query(int s,int e,int c,int ms,int me)
{if(s==ms&&e==me) //如果恰好是在[s,e]这个区间，那么记录下来最大成绩。{mg=max(mg,sgTree[c]);return;}int mid=(s+e)/2;if(mid>=me) query(s,mid,c*2,ms,me); //如果要搜索的区间的最大值不比mid大。那么，进入左儿子搜索else if(mid<ms) query(mid+1,e,c*2+1,ms,me); //同理else{query(s,mid,c*2,ms,mid); //这里，如果在左右儿子都有区间的话，那么就把[ms,me]也分成两个区间，分别搜索。query(mid+1,e,c*2+1,mid+1,me);}
}void update(int s,int e,int c)
{if(s==e&&s==ts){sgTree[c]=te;return;}int mid=(s+e)/2;if(mid>=ts) update(s,mid,c*2);if(ts>mid) update(mid+1,e,c*2+1);sgTree[c]=max(sgTree[c*2],sgTree[c*2+1]);
}void createTree(int s,int e,int c)
{if(s==e) //如果这个节点左右区间相等，那么就是一个学生，此时，输入成绩{scanf("%d",&sgTree[c]);return ;}int mid=(s+e)/2; //mid为此区间的中点createTree(s,mid,c*2); //创建左儿子节点createTree(mid+1,e,c*2+1); //创建右儿子节点sgTree[c]=max(sgTree[c*2],sgTree[c*2+1]); //这里采用后序遍历。因为只有，左右儿子都创建并且知道它们的最大成绩，这里才能比较并存储较大的成绩
}int main()
{char ch[2]; while(scanf("%d %d ",&n,&m)==2){createTree(1,n,1);for(int i=0;i<m;i++){scanf("%s %d %d",&ch,&ts,&te); //这里采用字符串输入，开始老是%c输入不正确，干脆就用字符串了。mg=0;if(ch[0]=='Q'){query(1,n,1,ts,te);printf("%d\n",mg);}if(ch[0]=='U')update(1,n,1);}}return 0;
}
这篇关于hdu 1754 (线段树)I Hate It的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
