# HDU-1754 线段树模板(单点更新)
## [HDU-1754](http://acm.hdu.edu.cn/showproblem.php?pid=1754)
板子题.
## 代码
没错从[这](https://www.cnblogs.com/geloutingyu/p/6958490.html)白嫖的. [这](https://blog.csdn.net/ADjky/article/details/53790151)还有个更全的.
```cpp
#include <iostream>
#include <stdio.h>
#include <string.h>
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std;
const int MAXN = 2e5 + 10;
int Max[MAXN << 2];//Max[rt]存储rt对应区间的最大值
void push_up(int rt){//更新rt的值
Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);
}
//建树
void build(int l, int r, int rt){//rt对应区间[l, r]
if(l == r){
scanf("%d", &Max[rt]);
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
push_up(rt);//向上更新
}
//单点替换
void updata(int p, int sc, int l, int r, int rt){//将p点值替换成sc
if(l == r){//找到p点
Max[rt] = sc;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) updata(p, sc, lson);
else updata(p, sc, rson);
push_up(rt);//向上更新节点
}
//求区间最值
int query(int L, int R, int l, int r, int rt){//查询[L, R]内最大值
if(L <= l && R >= r) return Max[rt];//当前区间[l, r]包含在[L, R]中
int cnt = 0;
int mid = (l + r) >> 1;
if(L <= mid) cnt = max(cnt, query(L, R, lson));//L在mid左边
if(R > mid) cnt = max(cnt, query(L, R, rson));//R在mid右边
return cnt;
}
int main(void){
int n, m;
while(~scanf("%d%d", &n, &m)){
// memset(Max, 0, sizeof(Max));
build(1, n, 1);
char ch[2];
int x, y;
while(m--){
scanf("%s%d%d", ch, &x, &y);
if(ch[0] == 'U') updata(x, y, 1, n, 1);
else printf("%d\n", query(x, y, 1, n, 1));
}
}
return 0;
}
```
![]()