• P3372 【模板】线段树 1

// - [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)
// O(log(n))

#include<stdio.h>

using namespace std;

/* 常量定义 
 * maxn:数据范围 
 */
const int maxn = 100001;
 
/* 全局变量 
 * n:点数 
 * m:操作数 
 * a(i):数组
 * f(i):下标为i的节点对应区间的元素和
 * v(i):下标为i的节点对应区间的每一个元素需要加的数值(懒标记) 
 */
int n = 0, m = 0, a[maxn];
long long f [maxn*4], v[maxn*4];

/* 建树 
 * k:下标为k的点 
 * l,r:区间的左端点、右端点 
 */
inline void buildtree(int k, int l, int r){
	v[k] = 0;
	if(l == r){
		f[k] = a[l];
		return;
	}
	int m = (l + r) >> 1;
	buildtree(k + k, l, m);
	buildtree(k + k + 1, m + 1, r);
	f[k] = f[k + k] + f[k + k + 1];
}

/* 区间值增加 
 * k:下标为k的点 
 * l,r:区间的左、右端点 
 * x,y:操作区间的左、右端点 
 * z:增加的值 
 */
inline void insert(int k, int l, int r, int x, int y, long long z){
	if(l == x && r == y){
		v[k] += z; 
		return;
	}
	f[k] += (y - x + 1) * z;
	int m = (l + r) >> 1;
	if(y <= m){
		insert(k + k, l, m, x, y, z);
	}else if(x > m){
		insert(k + k + 1, m + 1, r, x, y, z);
	}else{
		insert(k + k, l, m, x, m, z);
		insert(k + k + 1, m + 1, r, m + 1, y, z);
	}
}

/* 求区间和 
 * k:下标为k的点 
 * l,r:区间的左、右端点 
 * x,y:求和区间的左、右端点 
 * p:算过的区间v[]的和 
 */
long long calc(int k, int l, int r, int x, int y, int p){
	p += v[k];
	if(l == x && r == y){
		return p * (r - l + 1) + f[k];
	} 
	int m = (l + r) >> 1;
	if(y <= m){
		return calc(k + k, l, m, x, y, p);
	}else if(x > m){
		return calc(k + k + 1, m + 1, r, x, y, p);
	}else{
		return calc(k + k, l, m, x, m, p) + calc(k + k + 1, m + 1, r, m + 1, y, p);
	}
} 

int main(){
	freopen("P3372_8.in", "r", stdin);
	freopen("P3372_8.ans", "w", stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	buildtree(1,1,n);
	for(int i = 1; i <= m; i++){
		int t = 0;
		scanf("%d", &t);
		if(t == 1){
			int x = 0, y = 0;
			long long k = 0;
			scanf("%d%d%lld", &x, &y, &k);
			insert(1, 1, n, x, y, k);
		}else{
			int x = 0, y = 0;
			scanf("%d%d", &x, &y);
			printf("%lld\n", calc(1, 1, n, x, y, 0));
		}
	} 
	return 0;
}