线段树算法总结

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