暴力st表通过本题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
	ll l,r,k;
};
ll n,q,a[100010],logv[100010],st[20][100010],block,diff[100010];
vector <node> lazy;
void build(){
	for (ll i=1;i<=n;i++)  st[0][i]=a[i];
    for (ll j=1;(1<<j)<=n;j++){
        ll len=1<<j,mid=len>>1;
        for (int i=1;i+len-1<=n;i++){
            st[j][i]=st[j-1][i]+st[j-1][i+mid];
        }
    }
}
void update(ll l,ll r,ll k){
	lazy.push_back({l,r,k});
	if (lazy.size()>block){
		memset(diff,0,sizeof(diff));
		for (auto p:lazy)  diff[p.l]+=p.k,diff[p.r+1]-=p.k;
		for (int i=1;i<=n;i++){
			diff[i]+=diff[i-1];
			a[i]+=diff[i];	
		}
		lazy.clear();
		build();
	}
}
ll query(ll l,ll r){
	ll res=0,len=r-l+1,lll=l;
    for (ll j=logv[len];j>=0;j--)
        if (1<<j<=len)  res+=st[j][lll],lll+=1<<j,len-=1<<j;
    for (auto p:lazy){
    	ll L=max(l,p.l),R=min(r,p.r);
    	if (L<=R)  res+=(ll)(p.k*(R-L+1));
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for (int i=1;i<=n;i++)  cin>>a[i];
	logv[1]=0;
    for (ll i=2;i<=n;i++){
        logv[i]=logv[i/2]+1;
    }
    build();
    block=sqrt(n);
    while (q--){
    	ll op,x,y,k;
    	cin>>op; 
    	if (op==1){
    		cin>>x>>y>>k;
    		update(x,y,k);
		}else{
			cin>>x>>y;
			cout<<query(x,y)<<"\n";
		}
	}
	return 0;
}