编辑代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
#define left_son l,mid,root<<1
#define right_son mid+1,r,root<<1|1
using namespace std;
inline int read() {//quick read
	int x = 0; bool flag = 1; char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-')flag = 0; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	if (flag) return x;
	return ~(x - 1);
}
int n, m;
const int maxn = 1e5 + 5;
ll tag[maxn << 2],tree[maxn << 2];;
void push_up(int root) {//update father node
	tree[root] = tree[root << 1]+ tree[root << 1 | 1];
}
void push_down(int root,int len) {//root ->the tree's root,and the len ->the tree's length
	if (tag[root]) {
		tag[root << 1] += tag[root];//update left  children node
		tag[root << 1 | 1] += tag[root];//update right  children node
		tree[root << 1] += (len - (len >> 1)) * tag[root];//update father node
		tree[root << 1 | 1] += (len >> 1) * tag[root];
		tag[root] = 0;//inline 
	}
}
void Buildtree(ll l, ll r, ll root) {//build tree and input
	tag[root] = 0;
	if (l == r) {
		tree[root] =read();//read leaf's vaule
		return;
	}
	int mid = (l + r) >> 1;
	Buildtree(left_son);
	Buildtree(right_son);
	push_up(root);
}
void update(int a,int b,ll k,int l,int r,int root) {//add k into[a,b]
	if (a <= l && b >= r) {
		tree[root] += (r - l + 1) * k;
		tag[root] += k;//lazy-tag
		return;
	}
	push_down(root, r - l + 1);
	int mid = (r + l) >> 1;
	if (a <= mid)
		update(a, b, k,left_son);
	if (b > mid)
		update(a, b, k,right_son);
	push_up(root);
}
ll query(int a, int b, int l, int r, int root) {
	if (a <= l && b >=r)
		return tree[root];
	push_down(root, r - l + 1);
	int mid =(r + l) >> 1;
	ll ans = 0;
	if (a <= mid)
		ans += query(a, b,left_son);
	if (b > mid)
		ans += query(a, b, right_son); 
		return ans;
}
int main() {
	n = read(); m=read();
	Buildtree(1, n, 1);
	for (int i = 1; i <= m; i ++ ) {
		int input = read();
		if (input == 1) {//add k into tree[]
			int a = read(); int b = read(); int k = read();
			update(a, b, k, 1, n, 1);
		}
		else {//query
			int a = read(); int b = read();
			cout << query(a, b, 1, n, 1)<<endl;
		}
	}
	return 0;
}