输入描述:
输入包括多组测试数据。 每组输入第一行是两个正整数N和M（0 < N <= 30000,0 < M < 5000）,分别代表学生的数目和操作的数目。 学生ID编号从1编到N。 第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩 接下来又M行，每一行有一个字符C（只取‘Q’或‘U’），和两个正整数A,B,当C为'Q'的时候, 表示这是一条询问操作，他询问ID从A到B（包括A,B）的学生当中，成绩最高的是多少 当C为‘U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
输出描述:
对于每一次询问操作，在一行里面输出最高成绩.
输入例子1:
5 7 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 4 5 U 2 9 Q 1 5
输出例子1:
5 6 5 9
思路：包含典型的区间快速查找 和 修改操作
传统的遍历查找思路复杂度 O(N)级别
线段树 牺牲空间复杂度 其中树节点描述为： [left right]区间 区间内最大值
struct node { int left; int right; int max;//线段树 左右区间 区间内最大值 };采取build递归思路建立原始arr[]数组的 tree[]线段树
int arr[30001];//存放成绩 node tree[120000];//线段树节点
void build(int num,int left,int right) //以原始arr区间[left right] 构建到以num为根节点的 线段树上 { tree[num].left=left; tree[num].right=right; if(left==right) //叶子结点 { tree[num].max=arr[left]; return; } int mid=(left+right)>>1; build(num*2,left,mid); build(num*2+1,mid+1,right);//左右子树 tree[num].max=max(tree[num*2].max,tree[num*2+1].max);//取较大值 }线段树更新操作，先递归下降到最终叶子结点，在返回过程中修改包含该节点区间的max值 复杂度O(lgN)级别
void update(int num,int k,int new_data) //从tree[num]根节点的线段树开始 更新arr[k]的值为new_data { if(tree[num].left==tree[num].right) { if(tree[num].left==k) //抵达叶子结点 { tree[num].max=new_data; return; } } //同时 递归返回 修改包含这个节点的 线段 int mid=(tree[num].left+tree[num].right)>>1; if(k<=mid) //需要进入左子树 update(num*2,k,new_data); else update(num*2+1,k,new_data); //返回后 tree[num].max=max(tree[num*2].max,tree[num*2+1].max);//更新该节点的 最大值 }线段树查询操作 （查询区间内最大值） 传统思路O(N)复杂度 线段树O(lgN)复杂度
int my_max=-1; void query(int start,int end,int num) //查找Array 区间[start end]之间的最大值 从线段树tree[num]开始 { if(start>end) { int tmp=end; end=start; start=tmp; } if(tree[num].left>=start && tree[num].right<=end) //该线段树被包含在查找区间内 那么更新max { my_max=max(my_max,tree[num].max); return;//及时返回 } int mid=(tree[num].left+tree[num].right)>>1; if(start<=mid) //需要进一步访问左子树 query(start,end,num*2); if(end>mid) //需要进一步访问右子树 query(start,end,num*2+1); }主函数：
int main() { while(cin>>N>>M) { for(int i=1;i<=N;i++) //输入N个学术成绩 { cin>>arr[i]; } build(1,1,N);//从tree[1]开始构建以arr[1 N]的线段树 for(int i=0;i<M;i++) //操作 { char opera; int a; int b; cin>>opera; cin>>a>>b; if(opera=='U') //更新操作 { update(1,a,b); } else { my_max=-1; query(a,b,1);//从根节点tree[1]开始查询a b区间最大值 cout<<my_max<<endl; } } } }
