使用线段树解题
首先发现n很大,直接建树会爆空间,而且考虑到初始序列是固定的序列而且可以用求和公式求和,所以可以用动态开点
线段树维护区间和还有区间加法,其中区间加法的标记add仅在访问该节点下方(含该节点)的节点时有效,因为询问时访问下方节点会经过该结点,可以统计数值
对于上方的节点则在区间加法设置时将加完后的和(如区间\([l,r]加s让上方的节点sum值均加上(r-l+1)*s即可\))写入sum中
对于单点修改利用sum维护即可
求和访问顺序:求和所有子区间的sum,加上所有访问过的节点的add值(乘以区间长度)
时间复杂度\(O(qlogn)\)
空间复杂度\(O(qlogn)\)

注:该代码的线段树使用指针存储,加快效率

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
struct sp{
    sp *lc,*rc;
    ll sum;//sum保存区间和 
    ll add;//add保存区间加法 
    sp(){
        lc=rc=NULL;
    }
};
#define N 200001
int n,q;
sp *sgt;
inline ll sumarr(int l,int r){//l到r求和公式 
    return (ll)(r-l+1)*(r+l)/2;
}
inline sp* addsp(int l,int r){
    sp *res=new sp;
    res->add=0;
    res->sum=sumarr(l,r);
    return res;
}
#define mid ((l+r)>>1)
ll getval(sp *head,int k,int l,int r){//单点取值    
    if(l==r){
        return head->sum+head->add;
    }
    ll res=head->add;
    if(k<=mid){
        if(!head->lc) res+=k;
        else res+=getval(head->lc,k,l,mid); 
    }
    else{
        if(!head->rc) res+=k;
        else res+=getval(head->rc,k,mid+1,r);
    }
    return res;
}
void addval(sp *head,int k,int val,int l,int r){//单点加法 
    head->sum+=val;
    if(l==r) return;
    if(k<=mid){
        if(head->lc==NULL)  head->lc=addsp(l,mid);
        addval(head->lc,k,val,l,mid);
    } 
    else {
        if(head->rc==NULL) head->rc=addsp(mid+1,r);
        addval(head->rc,k,val,mid+1,r);
    }
    
}
void addsec(sp *head,int s,int t,int k,int l,int r){//区间加法 ,区间[s,t]加上k 
    if(s==l && t==r){
        head->add+=k;
        return;
    }
    head->sum+=(ll)(t-s+1)*k;
    if(s<=mid && NULL==head->lc) head->lc=addsp(l,mid);
    if(t>mid && NULL==head->rc) head->rc=addsp(mid+1,r);
    if(t<=mid) addsec(head->lc,s,t,k,l,mid);
    else if(s>mid) addsec(head->rc,s,t,k,mid+1,r);
    else{
        addsec(head->lc,s,mid,k,l,mid);
        addsec(head->rc,mid+1,t,k,mid+1,r);
    }
}
ll getsum(sp *head,int s,int t,int l,int r){//区间求和 
    if(s==l && t==r) return head->sum+(ll)(r-l+1)*head->add;
    ll res=(t-s+1)*head->add;
    if(t<=mid){
        if(!head->lc) res+=sumarr(s,t);
        else res+=getsum(head->lc,s,t,l,mid);
    }else if(s>mid){
        if(!head->rc) res+=sumarr(s,t);
        else res+=getsum(head->rc,s,t,mid+1,r);
    }else{
        if(!head->lc) res+=sumarr(s,mid);
        else res+=getsum(head->lc,s,mid,l,mid);
        if(!head->rc) res+=sumarr(mid+1,t);
        else res+=getsum(head->rc,mid+1,t,mid+1,r);
    }
    return res;
}
void freetree(sp *head){//指针内存释放 
    if(head->lc) freetree(head->lc);
    if(head->rc) freetree(head->rc);
    delete head;
}
#undef mid
int main(){
    int i,t,x,y,z;
    cin>>n>>q;
    sgt=addsp(1,n);
    for(i=1;i<=q;i++){
        cin>>t;
        switch(t){
            case 1:
                cin>>x>>y;
                addval(sgt,x,y-getval(sgt,x,1,n),1,n);
                break;
            case 2:
                cin>>x>>y>>z;
                addsec(sgt,x,y,z,1,n);
                break;
            case 3:
                cin>>x>>y;
                cout<<getsum(sgt,x,y,1,n);
                putchar('\n');
                break;
        }
    }
    freetree(sgt);
}