11376: 【原1376】求和
题目
题目描述
author: yuan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1376
题目描述
给你一个长度为n的序列,要求支持两种操作。
操作1:修改位置x的值为y;
操作2:求位置x至位置y的和。
输入说明
第一行输入一个整数n;
接下来一行n个整数表示数组;
接下来一行一个整数m表示操作数;
接下来每行三个整数type,x,y,分别表示操作类型和对应的x、y值;
输出说明
对于每个求和操作,输出一行一个值ans表示答案。
样例输入
5
1 2 3 4 5
4
2 1 5
2 2 4
1 3 7
2 3 3
样例输出
15
9
7
数据范围
对于50%的数据,1<=n,m<=1000;
对于100%的数据,1<=n,m<=100000,数字范围不超过100000;
yyong119's solution
#include <cstdio>
using namespace std;
const int MAX_N = 100010;
struct node {
int l, r;
long long key;
}tree[MAX_N << 2];
void buildtree(int node, int l, int r) {
if (l == r) {
scanf("%lld", &tree[node].key);
tree[node].l = l; tree[node].r = r;
return;
}
int mid = (l + r) >> 1;
buildtree(node << 1, l, mid);
buildtree(node << 1 | 1, mid + 1, r);
tree[node].l = l; tree[node].r = r;
tree[node].key = tree[node << 1].key + tree[node << 1 | 1].key;
}
void update(int node, int pos,int key) {
if (tree[node].l == tree[node].r) {
tree[node].key = key;
return;
}
int mid = (tree[node].l + tree[node].r) >> 1;
if (pos <= mid) update(node << 1, pos, key);
else update(node << 1 | 1, pos, key);
tree[node].key = tree[node << 1].key + tree[node << 1 | 1].key;
}
long long query(int node, int l, int r) {
if (tree[node].l == l && tree[node].r == r) return tree[node].key;
int mid = (tree[node].l + tree[node].r) >> 1;
if (r <= mid) return query(node << 1, l, r);
else if (l > mid) return query(node << 1 | 1, l, r);
else return query(node << 1, l, mid) + query(node << 1 | 1, mid + 1, r);
}
int main() {
int n; scanf("%d", &n);
buildtree(1, 1, n);
int m; scanf("%d", &m);
while (m--) {
int op, tmp1, tmp2;
scanf("%d%d%d", &op, &tmp1, &tmp2);
if (op == 2) printf("%lld\n", query(1, tmp1, tmp2));
else update(1, tmp1, tmp2);
}
return 0;
}