【急救】分块求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,m,a[maxn];
int t,sq;
struct node{
    int l,r,w,tag;
}p[maxn];
int pos[maxn];
void init()
{
    sq=sqrt(n);t=n/sq;
    for(int i=1;i<=t;i++)
    {
        p[i].l=(i-1)*sq+1;
        p[i].r=i*sq;
    }
    if(p[t].r<n)
    {
        t++;
        p[t].l=p[t-1].r+1;
        p[t].r=n;
    }
    for(int i=1;i<=n;i++)
        pos[i]=ceil((double)i/sq);
    for(int i=1;i<=n;i++)
        p[pos[i]].w+=a[i];
}
void upd(int l,int r,int x)
{
    int fr=pos[l],to=pos[r];
    if(fr==to)
    {
        for(int i=l;i<=r;i++)
            a[i]+=x;
        p[fr].w+=(r-l+1)*x;
        return;
    }
    for(int i=l;i<=p[fr].r;i++)
        a[i]+=x;
    p[fr].w+=(p[fr].r-l+1)*x;
    for(int i=fr+1;i<=to-1;i++)
        p[i].tag+=x;
    for(int i=p[to].l;i<=r;i++)
        a[i]+=x;
    p[to].w+=(r-p[fr].l+1)*x;
}
int ak(int l,int r)
{
    int fr=pos[l],to=pos[r],ret=0;
    if(fr==to)
    {
        for(int i=l;i<=r;i++)
            ret+=a[i]+p[fr].tag;
        return ret;
    }
    for(int i=l;i<=p[fr].r;i++)
        ret+=a[i]+p[fr].tag;
    for(int i=fr+1;i<=to-1;i++)
        ret+=p[i].w+p[i].tag*(p[i].r-p[i].l+1);
    for(int i=p[to].l;i<=r;i++)
        ret+=a[i]+p[to].tag;
    return ret;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    init();
    for(int i=1;i<=m;i++)
    {
        int opt,l,r,x;
        cin>>opt;
        if(opt==1)
        {
            cin>>l>>r>>x;
            upd(l,r,x);
        }
        else
        {
            cin>>l>>r;
            cout<<ak(l,r)<<endl;
        }
    }
    return 0;
}