单点修改，区间求和或区间询问最值(线段树)

【题目描述】

给定一个长度为n的非负整数序列，接下来有m次操作，操作共有3种：一是修改序列中某个元素的大小，二是求某个区间的所有元素的和，三是询问某个区间的最大值。整数序列下标从1开始。n<=10^5, m<=10^5。

【输入描述】

第一行2个整数n和m, 分别 表示整数序列的元素个数和操作次数；

接下来一行就是这n个非负整数, 每个整数都不超过10^8；

接下来m行，每行都有三个整数k, a, b;

如果k是0的话，就表示把原序列中的第a个位置上的数改为b,b也是不超过10^8的非负整数。

如果k是1的话，就表示询问区间[a, b]的最大值， 如果k是2的话就表示询问区间[a, b]的元素和。

【输出描述】

对于每个k为1或2的询问输出相对应的结果，每个输出结果占一行。

【输入样例】

10 4
5 2 3 4 7 9 5 8 6 2
0 5 9
1 2 5
0 8 6
2 7 10

【输出样例】

9
19

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
struct node {int l, r, mx;ll s;
};
node xdt[4*N];
int n, m, p, l, r, x, y, a[N];
void build(int k, int l, int r) {xdt[k].l = l;  xdt[k].r = r;if (l==r) {xdt[k].s = a[l];xdt[k].mx = a[l];return;}int mid = (xdt[k].l + xdt[k].r) / 2;build(k*2, l, mid);build(k*2+1, mid+1, r);xdt[k].s = xdt[k*2].s + xdt[k*2+1].s;xdt[k].mx = max(xdt[k*2].mx, xdt[k*2+1].mx);
}
void change(int k, int x, int y) {if (xdt[k].l == x && xdt[k].r == x) {xdt[k].s = y;xdt[k].mx = y;return;	}int mid = (xdt[k].l + xdt[k].r) / 2;if (x <= mid) change(k*2, x, y);else change(k*2+1, x, y);xdt[k].s = xdt[k*2].s + xdt[k*2+1].s;xdt[k].mx = max(xdt[k*2].mx, xdt[k*2+1].mx);
}
long long find_s(int k, int l, int r) {if (xdt[k].l == l && xdt[k].r == r) {return xdt[k].s;}int mid = (xdt[k].l + xdt[k].r) / 2;if (l > mid) return find_s(k*2+1, l, r);if (r <= mid) return find_s(k*2, l, r);return find_s(k*2, l, mid) + find_s(k*2+1, mid+1, r);
}
int find_mx(int k, int l, int r) {if (xdt[k].l == l && xdt[k].r == r) {return xdt[k].mx;}int mid = (xdt[k].l + xdt[k].r) / 2;if (l > mid) return find_mx(k*2+1, l, r);if (r <= mid) return find_mx(k*2, l, r);return max(find_mx(k*2, l, mid), find_mx(k*2+1, mid+1, r));
}
int main() {scanf("%d%d", &n, &m);for (int i=1; i<=n; i++) scanf("%d", &a[i]);build(1, 1, n);for (int i=1; i<=m; i++) {scanf("%d", &p);if (p==0) {scanf("%d%d", &x, &y);change(1, x, y);} if (p==1) {scanf("%d%d", &l, &r);printf("%d\n", find_mx(1, l, r));}if (p==2) {scanf("%d%d", &l, &r);printf("%lld\n", find_s(1, l, r));}}return 0;
}