线段树算法总结
P1531 I Hate It
webiste:未知网址
题目背景
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。
题目描述
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
输入格式
第一行，有两个正整数 n 和 m（0<n≤2×105,0<m≤2×105），分别代表学生的数目和操作的数目。学生 ID 编号分别从 1 编到 n。
第二行包含 n 个整数，代表这 n 个学生的初始成绩，其中第 i 个数代表 ID 为 i 的学生的成绩，保证学生的成绩为 1∼109 之间的正整数。
接下来有 m 行。每一行有一个字符 c（只取Q或U），和两个正整数 a，b。
- 当 c 为
Q的时候，表示这是一条询问操作，它询问 ID 从 a 到 b（包括 a,b） 的学生当中，成绩最高的是多少； - 当 c 为
U的时候，表示这是一条更新操作，如果当前 a 学生的成绩低于 b，则把 ID 为 a 的学生的成绩更改为 b，否则不改动。
思路
这是一道较为简单的线段树模板，主要运用分治思想，把1~n分成许多部分，像组长一样每个人都有自己管辖的区间，把每一次拆分标序号，单点修改更新最大值，再层层比较，最后比出区间最大值。
代码
#include<bits/stdc++.h> using namespace std; int a[200005],tree[800005]; void build(int o,int l,int r){ if(l == r){ tree[o] = a[l]; return; } int mid = (l+r)/2; build(o*2,l,mid); build(o*2+1,mid+1,r); tree[o] = max(tree[o*2],tree[o*2+1]); } void updata(int o,int l,int r,int p,int k){ if(l == r){ tree[o] = max(tree[o],k); return; } int mid = (l+r)/2; if(p<=mid) updata(o*2,l,mid,p,k); else updata(o*2+1,mid+1,r,p,k); tree[o] = max(tree[o*2],tree[o*2+1]); } int query(int o,int l,int r,int x,int y){ if(x<=l&&r<=y){ return tree[o]; } int mid = (l+r)/2,ans = 0; if(x<=mid) ans = max(ans,query(o*2,l,mid,x,y)); if(y>mid)ans = max(ans,query(o*2+1,mid+1,r,x,y)); return ans; } int main(){ int n,m; cin>>n>>m; for(int i = 1;i<=n;i++)cin>>a[i]; build(1,1,n); char op; int x,y; for(int i = 1;i<=m;i++){ cin>>op>>x>>y; if(op == 'U'){ updata(1,1,n,x,y); }else{ cout<<query(1,1,n,x,y)<<endl; } } return 0; }