线段树一

像素君

2025-09-14 18:09:28

发布于：北京

30阅读

0回复

0点赞

初赛单选题综合练习（提交后有解析）：
https://kaoshi.wjx.top/vm/PKXtqcp.aspx#

初赛阅读题练习：
试卷：https://www.acgo.cn/contest/question/12850?matchRoundId=12850&examId=69129&openLevel=2&teamCode=1780883567832375296
邀请码：f4D6

复习

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
	ll l, r;
	ll sum;
} tree[2000005];
ll n, m;
ll s[500005];
//线段树的构造
void build(ll l, ll r, ll p) {
	tree[p].l = l, tree[p].r = r;
	if (l == r) {
		tree[p].sum =  s[l];
		return ;
	}
	ll mid = (l + r) / 2;
	build(l, mid, p * 2);
	build(mid + 1, r, p * 2 + 1);
	tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
//将数组第 x 个数 +c
void update(ll x, ll c, ll p) {
	if (tree[p].l == tree[p].r) {
		tree[p].sum += c;
		return ;
	}
	ll mid = (tree[p].l + tree[p].r) / 2;
	if (x <= mid) {
		update(x, c, p * 2);
	} else {
		update(x, c, p * 2 + 1);
	}
	tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
//查询 [l,r] 区间和 p 所管辖区间“交叉部分”的“区间和”
ll query(ll l, ll r, ll p) {
	//如果 p 所管辖区间被 [l,r] 区间完全包裹
	if (tree[p].l >= l && tree[p].r <= r) {
		return tree[p].sum;
	}
	ll ans = 0;
	ll mid = (tree[p].l + tree[p].r) / 2;
	//[l,r] 与左孩子管辖区间有交叉部分
	if (l <= mid) {
		ans += query(l, r, p * 2);
	}
	//[l,r] 与右孩子管辖区间有交叉部分
	if (r > mid) {
		ans += query(l, r, p * 2 + 1);
	}
	return ans;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	build(1, n, 1);
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1) {
			update(x, y, 1);
		} else {
			cout << query(x, y, 1) << endl;
		}
	}
	return 0;
}