分块

与线段树类似。是暴力的优化版，详细见下两个链接

https://www.cnblogs.com/milky-w/p/8447724.html

https://www.cnblogs.com/Miracevin/p/9403620.html

板子：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5;
int n, m, a[N], st[N], ed[N], pos[N], sum[N], add[N];
int op, x, y, k;
void init()
{
	int block=sqrt(n);
	int t=n/block;
	
	if (n%block) t++;
	
	for (int i=1; i<=t; i++)
	{
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
    ed[t]=n;
	for (int i=1; i<=n; i++) pos[i]=(i-1)/block+1;
	
	for (int i=1; i<=t; i++)
		for (int j=st[i]; j<=ed[i]; j++) sum[i]+=a[j];
}
void Add(int L, int R, int d)
{
	int p=pos[L], q=pos[R];
	if (p==q)
	{
		for (int i=L; i<=R; i++) a[i]+=d;
		sum[p]+=d*(R-L+1);
	}
	else
	{
		for (int i=p+1; i<=q-1; i++) add[i]+=d;
		
		for (int i=L; i<=ed[p]; i++) a[i]+=d;
		sum[p]+=d*(ed[p]-L+1);
		
		for (int i=st[q]; i<=R; i++) a[i]+=d;
		sum[q]+=d*(R-st[q]+1);
	}
}
int query(int L, int R)
{
	int p=pos[L], q=pos[R], ans=0;
	if (p==q)
	{
		for (int i=L; i<=R; i++) ans+=a[i];
		ans+=add[p]*(R-L+1);
	}
	else
	{
		for (int i=p+1; i<=q-1; i++) ans+=sum[i]+add[i]*(ed[i]-st[i]+1);
		
		for (int i=L; i<=ed[p]; i++) ans+=a[i];
		ans+=add[p]*(ed[p]-L+1);
		
		for (int i=st[q]; i<=R; i++) ans+=a[i];
		ans+=add[q]*(R-st[q]+1);
	}
	return ans;
}
signed main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%lld", &a[i]);
	init();
	
	while (m--)
	{
		scanf("%d", &op);
		if (op==1)
		{
			scanf("%d%d%lld", &x, &y, &k);
			Add(x, y, k);
		}
		else if (op==2)
		{
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", query(x, y));
		}
	}
	return 0;
}