题意

即维护一棵线段树，支持单点修改+区间查询。

芝士——线段树

线段树（Segment Tree）是一种树状数据结构，主要用来高效处理区间查询（RMQ）与区间修改问题。

下图就是一棵简单的线段树，每一个节点都是其子节点之和，叶子结点用于存储数值，非叶子结点用于维护区间和。

graph TD
    A["[1,4] sum=10"]-->B["[1,2] sum=3"]
    A-->C["[3,4] sum=7"]
    B-->D["[1,1] sum=1"]
    B-->E["[2,2] sum=2"]
    C-->F["[3,3] sum=3"]
    C-->G["[4,4] sum=4"]

我们可以用一个结构体来存储线段树，但由于二叉树的性质，对于编号为 $n$ 的节点，其左右子节点分别为 $2n$ 和 $2n+1$，我们通常可以用一个数组直接存储线段树（不过需要注意，由于线段树需要维护区间和，所以通常要开 $4$ 倍空间，如果你想省空间而不开 $4$ 倍，就等着 RE 吧 doge）。

由于线段树是基于分治思想实现的，所以可以把单次查询或修改的复杂度降到 $\mathcal{O}(\log n)$。

总时间复杂度：$\mathcal{O}(m\log n)$。

标程

#include<bits/stdc++.h>
#define int long long
using namespace std;
int tree[800005],a[200005];//树要开 4 倍
inline void push_up(int id)//上传，注意不要和lazy_tag的下传搞混
{
    tree[id]=tree[id<<1]+tree[id<<1|1];//更新父节点为子节点之和
}
inline void build(int id,int l,int r)//建树
{
    if(l==r)//到叶子节点了
    {
        tree[id]=a[l];//赋值
        return ;
    }
    else
    {
        int mid=l+r>>1;//分治
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
        push_up(id);
        return ;
    }
}
inline int query(int id,int l,int r,int L,int R)//区间查询
{
    if(L<=l&&R>=r)return tree[id];//完全包含
    int mid=l+r>>1;
    int ans=0;
    if(L<=mid)ans+=query(id<<1,l,mid,L,R);//搜左子树
    if(R>mid)ans+=query(id<<1|1,mid+1,r,L,R);//右子树
    return ans;
}
inline void update(int id,int l,int r,int pos,int x)//单点修改
{
    if(l==r)
    {
        tree[id]=x;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)update(id<<1,l,mid,pos,x);
    else update(id<<1|1,mid+1,r,pos,x);
    push_up(id);
}
signed main() 
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);//除非动态开点，否则都要建树
    while(m--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)
        {
            update(1,1,n,l,r);
        }
        else if(op==2)
        {
            cout<<query(1,1,n,l,r)<<endl;
        }
    }
    return 0;
}