线段树一
2025-09-14 18:09:28
发布于：北京
38阅读
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;
}
有帮助，赞一个