题目描述

给定 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

#include <iostream>
#include <stdio.h>

using namespace std;

struct node{
    int sum, leftn, rightn;
    node *left, *right;
    node(int leftn, int rightn):sum(0), leftn(leftn), rightn(rightn), left(NULL), right(NULL){}
};

int n, in[100010];

node* build(int left, int right){
    node *p = new node(left, right);
    if(left == right){
        p->sum = in[left];
        p->leftn;
        return p;
    }
    int mid = (left+right)/2;
    p->left = build(left, mid);
    p->right = build(mid+1, right);
    p->sum = p->left->sum + p->right->sum;
    return p;
}

int get(node *head, int left, int right){
    //printf("%d %d\n", head->leftn, head->rightn);
    if(head->leftn == left && head->rightn == right) return head->sum;

    int ans = 0;
    if(left <= head->left->rightn){
        if(right <= head->left->rightn) ans += get(head->left, left, right); // 只在左边
        else ans += get(head->left, left, head->left->rightn); // 还有在右边
    }

    if(right >= head->right->leftn){
        if(left >= head->right->leftn) ans += get(head->right, left, right); // 只在右边
        else ans += get(head->right, head->right->leftn, right); // 还有在左边
    }
    return ans;
}

void add(node *head, int ind, int num){
    if(head->leftn == head->rightn){
        head->sum += num;
        return;
    }
    if(ind >= head->left->leftn && ind <= head->left->rightn) add(head->left, ind, num);
    else add(head->right, ind, num);

    head->sum = head->left->sum + head->right->sum;
}

int main(){
    int m, k, a, b;
    node* head;
    cin >>n >>m;
    for(int i = 1; i <= n; i++) cin >>in[i];
    head = build(1, n);

    for(int i = 0; i < m; i++){
        cin >>k >>a >>b;
        if(k) add(head, a, b);
        else cout <<get(head, a, b) <<endl;
    }
    return 0;
}