欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 美景 > 单点修改,区间求和或区间询问最值(线段树)

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

2025/2/24 12:33:04 来源:https://blog.csdn.net/2301_79534589/article/details/144041924  浏览:    关键词:单点修改,区间求和或区间询问最值(线段树)

【题目描述】

给定一个长度为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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词