Skip to content

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;
}