【模板】树状数组区间修改、区间查询

/*
区间修改， 区间查询；
原 ： a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + ….., + an;
差分：b1 + b2 + b3 + b4 + b5 + b6 + b7 + b8 + …… + bn;
求和 ： a1 = b1
		   a2 = b1 + b2;
			a3 = b1 + b2 + b3;
			a4 = b1 + b2 + b3 + b4;
			……
			an = b1 + b2 + b3 + b4 + …… + bn;

a1 + a2 + ….. + ax = ans = 
for(int i = 1; i <= x; i++)
{
	for(int k = 1; k <= i; k++)
	{
		ans += b[i];
	}
}
= 
for(int I = 1; I <= x; i++)
{
	Ans += (x – I + 1) * bi;
}
=
For(int I =1; I <= x; i++)
{
	Ans += (x + 1) * bi - I * bi;
}
需要2个差分；
一个维护bi, 一个维护I * bi;
*/
#include<bits/stdc++.h>

using namespace std;

int n, m;
long long a[10000010], b1[10000010], b2[10000010];

int lb(int x)
{
	return x & (-x);
}

void updata(int pos, int val)
{
	for(int i = pos; i <= n; i += lb(i))
	{
		b1[i] += val;
		b2[i] += pos * val;
	}
}

long long getsum(int pos)
{
	long long ans = 0;
	for(int i = pos; i > 0; i -= lb(i))
	{
		ans += (pos + 1) * b1[i] - b2[i]; 
	}
	return ans;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		updata(i, a[i] - a[i - 1]);
	}
	for(int i = 1, q, c, d, e; i <= m; i++)
	{
		scanf("%d", &q);
		if(q == 1)
		{
			scanf("%d%d%d", &c, &d, &e);
			updata(c, e);
			updata(d + 1, -e);
		}
		else 
		{
			scanf("%d%d", &c, &d);
			printf("%lld\n", getsum(d) - getsum(c - 1));
		}
	}
	return 0;
}