线段树

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 1e5 + 5;
void build(int root, int a[], int sum[], int start, int end)
{
    //printf("当前root是%d,当前start是%d,当前end是%d\n",root,start,end);
    if (start == end)
    {
        sum[root] = a[start];
        //printf("a[%d] = %d a[%d] = %d\n",start,a[start],root,a[root]);
        return;
    }
    int mid = (start + end) / 2;
    int left_node = 2 * root + 1;
    int right_node = 2 * root + 2;
    build(left_node, a, sum, start, mid);
    build(right_node, a, sum, mid + 1, end);
    sum[root] = sum[left_node] + sum[right_node];
    //printf("a[root] = %d\n",a[root]);
}
void show(int sum[], int n)
{
    for (int i = 0; i < n; i++)
        cout << sum[i] << " ";
}
void update(int root, int a[], int sum[], int start, int end, int idx, int val)
{
    if (start == end)
    {
        a[idx] = val;
        sum[root] = val;
        return;
    }
    int mid = (start + end) / 2;
    int left_node = 2 * root + 1;
    int right_node = 2 * root + 2;
    if (idx <= mid && idx >= start)
        update(left_node, a, sum, start, mid, idx, val);
    else
        update(right_node, a, sum, mid + 1, start, idx, val);
    sum[root] = sum[left_node] + sum[right_node];
}
int query(int root, int a[], int sum[], int start, int end, int ran1, int ran2)
{
    if (end<ran1 || start>ran2)return 0;
    if (start == end)return sum[root];
    if (start >= ran1 && end <= ran2)
    {
        return sum[root];
    }
    int mid = (start + end) / 2;
    int left_node = 2 * root + 1;
    int right_node = 2 * root + 2;
    int ans1 = query(left_node, a, sum, start, mid, ran1, ran2);
    int ans2 = query(right_node, a, sum, mid+1,end, ran1, ran2);
    return ans1 + ans2;
}
int main(void)
{
    int a[maxn];
    int sum[maxn];
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    build(0, a, sum, 0, n - 1);
    show(sum, n);
    cout << endl;
    while (m--)
    {
        int x; cin >> x;
        if (x == 1)
        {
            int u, o; cin >> u >> o;
            update(0, a, sum, 0, n - 1, u, o);
            //show(sum,n);
            //show(a,n);
        }
        if (x == 2)
        {
            int u, o; cin >> u >> o;
            int s = query(0, a, sum, 0, n - 1, u, o);
            cout << s << endl;
        }
    }

}