题目描述

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式
第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。

第二行包含 n 个整数，表示完整数列。

接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。

数列从 1 开始计数。

输出格式
输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。

数据范围
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n

样例

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例：

11
30
35

C++ 代码

#include<iostream>

int n, m;
int ali[100007] = {};
int sec_tree[100007] = {};

void build_tree(int L, int R, int root)
{
    if (L == R)
    {
        sec_tree[root] = ali[L];
        return;
    }
    int mid = (L + R) >> 1;
    int ans = 0;
    build_tree(L, mid, root * 2);
    build_tree(mid + 1, R, root * 2 + 1);
    sec_tree[root] = sec_tree[root * 2] + sec_tree[root * 2 + 1];
    return;
}

void updata(int L, int R, int idx, int root, int data)
{
    if (L == R) { sec_tree[root] += data; return; }//L与R表示范围，赋值应该再root处，这个点找了好久，
    int mid = (L + R) >> 1;
    if (idx <= mid)updata(L, mid, idx, root * 2, data);
    else updata(mid + 1, R, idx, root * 2 + 1, data);
    sec_tree[root] = sec_tree[root * 2] + sec_tree[root * 2 + 1];
    return;
}

int query(int now_L, int now_R, int ans_L, int ans_R, int root)
{
    if (now_L >= ans_L && now_R <= ans_R)return sec_tree[root];//定下来的范围不用更改，只要用现在的
    //L和R与原定的L和R相比若现在的L，R范围在规定范围之内，即可返回询问的值
    int mid = (now_L + now_R) >> 1;
    if (ans_L > mid)return query(mid + 1, now_R, ans_L, ans_R, root * 2 + 1);
    else if (ans_R <= mid)return query(now_L, mid, ans_L, ans_R, root * 2);
    else return query(now_L, mid, ans_L, ans_R, root * 2) + query(mid + 1, now_R, ans_L, ans_R, root * 2 + 1);
}

int main(void)
{
    std::ios_base::sync_with_stdio(false);
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++)std::cin >> ali[i];
    build_tree(1, n, 1);
    while (m--)
    {
        int k, a, b;
        std::cin >> k >> a >> b;
        if (k)updata(1, n, a, 1, b);
        else printf("%d\n", query(1, n, a, b, 1));
    }


    return 0;
}