代码如下

#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
const int Maxn=1000001,Maxm=1001; 
ULL ans,b[Maxm];
int a[Maxn];
int l[Maxm],r[Maxm],belong[Maxm],biao[Maxm],block,m,c,d,e,f,p,q,len,T;
void rebuild(){
	len=sqrt(m);
	block=(m-1)/len+1;
	for(int i=1;i<=block;i++){
		l[i]=r[i]-1;r[i]=i*block;
	}
	r[block]=m;
    for(int i=1;i<=block;i++){
       for(int j=l[i];j<=r[i];j++){
       	belong[a[j]]=i;
       	b[i]+=a[j];
	   }
	}
}
void check(int x,int y){
	p=belong[x];
	q=belong[y];
	if(p==q){
		for(int i=x;i<=y;i++){
			ans+=a[i]+biao[p];
		}
		cout<<ans<<endl;ans=0;
	}
    else{
    	for(int i=x;i<=r[p];i++){
    		ans+=a[i]+biao[p];
		}
    	for(int i=l[q];i<=y;i++){
    		ans+=a[i]+biao[p];
		}
		for(int i=p+1;i<=q-1;i++){
			ans+=b[i]+block*biao[i];
		}
		cout<<ans<<endl;ans=0;
	}
}
void change(int x,int y,int w){
	p=belong[x];
	q=belong[y];
	if(p==q){
	for(int i=x;i<=y;i++){
	a[i]+=w;b[p]+=w;
		}}
	else{
		for(int i=x;i<=r[p];i++){
    	a[i]+=w;b[p]+=w;
		}
		for(int i=l[q];i<=y;i++){
    	a[i]+=w;b[q]+=w;
		}
		for(int i=p+1;i<=q-1;i++){
		biao[i]+=w;
		}
	}
}
int main(){ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>T;
    for(int i=1;i<=m;i++){
    	cin>>a[i]; 
	}
	for(int i=1;i<=T;i++){
		cin>>c>>d>>e;
		if(c==2)check(d,e);
		else{
		cin>>f;change(d,e,f);
		}
	}
	}