成功代码 线段树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll a[100005], tree[100005 << 2], mark[100005 << 2];//mark:懒标记 tree：树

int build(ll l, ll r, ll p){ //建树
	if(l == r){  //到达叶节点  返回
		tree[p] = a[l];
		return 0;
	}
	ll mid = (l + r) / 2;  
	build(l, mid, p * 2);	//p*2左儿子的下标
	build(mid + 1, r, p * 2 + 1); //p*2+1左儿子的下标
	tree[p] = tree[p * 2] + tree[p * 2 + 1];//父节点=左儿子+右儿子
	return 0;
	
}

int push_down(ll p, ll len){
	mark[p * 2] += mark[p];
	mark[p * 2 + 1] += mark[p]; //把懒标记下传到子节点
	tree[p * 2] += (len - len / 2) * mark[p];
	tree[p * 2 + 1] += (len / 2) * mark[p];//以懒标记更新子节点
	mark[p] = 0;//更新父节点懒标记
	return 0;
}
//参数：l， r:目标
//cl, cr：当前
//d:题目中的k
//p:节点下标
int add(ll l, ll r, ll d, ll p, ll cl, ll cr){
	if(cr < l or cl > r) return 0;//在目标区间外
	if(cr <= r and cl >= l){//全部在目标区间内
		tree[p] += (cr - cl + 1) * d;
		if(cr > cl) mark[p] += d;//不在叶节点，记录懒标记
		return 0;
	}//否则不完全在目标区间内
	ll mid = (cl + cr) / 2;
	push_down(p, cr - cl + 1);//向下传递懒标记
	add(l, r, d, p * 2, cl, mid);//计算子节点
	add(l, r, d, p * 2 + 1, mid + 1, cr);//计算子节点
	tree[p] = tree[p*2] + tree[p*2+1];//更新
	return 0;
}

ll query(ll l, ll r, ll p, ll cl, ll cr){//求和
	if(cr < l or cl > r) return 0;//不在区间内返回0
	if(cr <= r and cl >= l){
		return tree[p];//完全在区间内全部返回
	}//否则不完全在目标内
	ll mid = (cl + cr) / 2;
	push_down(p, cr - cl + 1);//向下传递标记
	return query(l, r, p * 2, cl, mid) + query(l, r, p * 2 + 1, mid + 1, cr);//左子+右子
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	build(1, n, 1);
	while(m--){
		short method;
		cin >> method;
		if(method == 2){
			ll l, r;
			cin >> l >> r;
			cout << query(l, r, 1, 1, n) << endl;
		}else{
			ll l, r, k;
			cin >> l >> r >> k;
			add(l, r, k, 1, 1, n);
		}
	}
	return 0;
}