线段树Segment tree（1）：单点修改，区间查询

问题描述： 给定数列a[1],a[2],…,a[N],依次进行Q次操作，操作有两类：
1 i x: 给定i，x，将a[i]加上x
2 l r: 给定i，x，求 ∑ i = l r \sum_{i=l}^r ∑i=lr​a[i]

代码

// TSWorld
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 400005;

struct Node
{
    long long left;
    long long right;
    long long sum;
    struct Node *LeftNode;
    struct Node *RightNode;
};

long long number[N];

inline void Built(struct Node *cur,int l,int r)
{
    cur->left = l;
    cur->right = r;
    if(l==r)
    {
        cur->LeftNode = NULL;
        cur->RightNode = NULL;
        cur->sum = number[l];
        return;
    }
    else
    {
        cur->LeftNode = new Node;
        cur->RightNode = new Node;
        Built(cur->LeftNode,l,(l+r)/2);
        Built(cur->RightNode,(l+r)/2+1,r);
    }
    cur->sum = cur->LeftNode->sum + cur->RightNode->sum;
}

inline long long query(struct Node *cur,long long l,long long r)
{
    // 查询区间覆盖了当前节点
    if((l <= cur->left)&&(cur->right <=r))
        return cur->sum;
    else
    {
        long long ans = 0;

        // 当前节点左子树有查询区间
        if(l <= (cur->left + cur->right)/2)
            ans += query(cur->LeftNode,l,r);
        // 当前节点右子树有查询区间
        if(r > (cur->left + cur->right)/2)
            ans += query(cur->RightNode,l,r);   
        return ans;
    }
}

inline void updata(struct Node *cur,long long address,long long data)
{
    if(cur->left == cur->right)
    {
        cur->sum += data;
        return;
    }

    if(address <= (cur->left + cur->right)/2)
        updata(cur->LeftNode,address,data);
    else
        updata(cur->RightNode,address,data);

    cur->sum = cur->LeftNode->sum + cur->RightNode->sum;
}
int main()
{
    long long n = 0,q = 0,cmd = 0;
    long long x = 0,y = 0;
    struct Node *root = new Node;
    scanf("%lld%lld",&n,&q);

    for(int i = 1;i <= n;i++)
        scanf("%lld",&number[i]);

    Built(root,1,n);

    for(int i = 1;i <= q;i++)
    {
        scanf("%lld%lld%lld",&cmd,&x,&y);
        if(cmd == 1)
            updata(root,x,y);
        else
            printf("%lld\n",query(root,x,y));
    }
    return 0;
}