线段树板子

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500100;
typedef long long LL;
#define lc p << 1
#define rc p << 1 | 1
int n,m,w[N];
struct node
{
    LL l,r,sum,add;
}tr[4*N];
void push_down(int p)
{
    if(tr[p].add)
    {
        tr[lc].sum += tr[p].add*(tr[lc].r  - tr[lc].l + 1);
        tr[rc].sum += tr[p].add*(tr[rc].r - tr[rc].l + 1);
        tr[lc].add += tr[p].add;
        tr[rc].add += tr[p].add;
        tr[p].add = 0;
    }
}
void push_up(int p)
{
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void build(int p,int l,int r)
{
    tr[p] = {l,r,w[l],0};
    if(l == r) return;
    int mid = l +r >>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    push_up(p);
}
LL query(int p,int x,int y)
{
    if(x<=tr[p].l&&y>=tr[p].r) return tr[p].sum;
    int mid = tr[p].l + tr[p].r >> 1;
    push_down(p);
    LL sum = 0;
    if(x<=mid) sum+=query(lc,x,y);
    if(y>mid) sum += query(rc,x,y);
    return sum;
}
void update(int p,int x,int y,int k)
{
    if(x<=tr[p].l&&y>=tr[p].r)
    {
        tr[p].sum += (tr[p].r - tr[p].l + 1)*k;
        tr[p].add += k;
        return;
    }
    push_down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if(x<=mid) update(lc,x,y,k);
    if(y>mid) update(rc,x,y,k);
    push_up(p);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op == 2) cout<<query(1,x,y)<<endl;
        else
        {
            update(1,x,x,y);
        }
    }
    return 0;
}