思路来源于洛谷题解
#include<bits/stdc++.h>
using namespace std;
//用longlong 存sum;
const int N = 100010;
typedef long long LL;
typedef struct Node
{
int le;
int ri;
LL sum = 0;
LL lazy = 0;
}trnode[4*N];
int a[N];
trnode tr;
void bui_tr(int x, int L,int R)
{
//对于每一个子问题要做什么操作
tr[x].le = L;
tr[x].ri = R;
if(tr[x].le == tr[x].ri)
{
tr[x].sum = a[L];
return;
}
int mid = tr[x].le + tr[x].ri >> 1;
// 分解
bui_tr(2 * x, L, mid);
bui_tr(2 * x + 1, mid + 1, R);
tr[x].sum = tr[2 * x].sum + tr[2 * x + 1].sum; //合并
}
void spread(int x)
{
if(tr[x].lazy)
{
tr[2 * x].lazy += tr[x].lazy;
tr[2 * x + 1].lazy += tr[x].lazy;
tr[2 * x].sum += (LL)(tr[2 * x].ri - tr[2 * x].le + 1) * tr[x].lazy;
tr[2 * x + 1].sum += (LL)(tr[2 * x + 1].ri - tr[2 * x + 1].le + 1) * tr[x].lazy;
tr[x].lazy = 0;
}
}
void change(int x, int l, int r, int z)//修改区间和
{
if(l <= tr[x].le && r >= tr[x].ri)
{
tr[x].lazy += z;
tr[x].sum += (LL)(tr[x].ri - tr[x].le + 1) * z;
return;
}
else spread(x);
int mid = tr[x].le + tr[x].ri >> 1;
if(l <= mid) change(2 * x, l, r, z);
if(r >= mid + 1) change(2 * x + 1, l, r, z); //不能写成else if
tr[x].sum = tr[2 * x].sum + tr[2 * x + 1].sum;
}
LL query_tr(int x, int l, int r)
{
/*if(tr[x].le == l && tr[x].ri == r) return tr[x].sum;
int mid = tr[x].le + tr[x].ri >> 1;
if(r <= mid) query_tr(2 * x, l, r);
else if(l >= mid + 1) query_tr(2 * x + 1, l, r);
else
{
LL sum1 = query_tr(2 * x, l, mid);
LL sum2 = query_tr(2 * x + 1, mid + 1, r);
return (LL)sum1 + sum2;*/ //由于lazy操作的存在此时不可以这样写query 否则会导致出错 没有lazy的下放
//}
if(tr[x].le >= l && tr[x].ri <= r) return tr[x].sum;
spread(x);
int mid = tr[x].le + tr[x].ri >> 1;
LL ans = 0;
if(l <= mid) ans += query_tr(2 * x, l, r);
if(r >= mid + 1) ans += query_tr(2 * x + 1, l, r);
return ans;
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++) scanf("%d",&a[i]);
bui_tr(1, 1, n);
//printf("%lld",query_tr(1, 2, 4));
while(m --)
{
int k1;
scanf("%d",&k1);
if(k1 == 1)
{
int x, y, k;
scanf("%d%d%d",&x,&y,&k);
//进行修改操作
change(1, x, y, k);
}
else
{
int x, y;
scanf("%d%d",&x,&y);
printf("%lld\n",query_tr(1, x, y));
}
}
return 0;
}