竖琴

静态线段树（动态开点的后边再补

#include<cstdio>
typedef long long ll;
#define INT 100005
struct node{
	ll data;
	ll l,r;
	ll lztag;
} tr[INT*4];
ll data[INT];
void segtreebuild(ll p,ll l,ll r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].data=data[l];
	}
	else{
		ll mid=(l+r)/2;
		segtreebuild(2*p,l,mid);
		segtreebuild(2*p+1,mid+1,r);
		//在这里进行区间合并操作
		tr[p].data=tr[2*p].data+tr[2*p+1].data;
	}
}
//懒标记传递
void pushdown(ll p) {
    if (tr[p].lztag != 0) {
        tr[p*2].lztag += tr[p].lztag;
        tr[p*2+1].lztag += tr[p].lztag;
        tr[p*2].data += tr[p].lztag * (tr[p*2].r - tr[p*2].l + 1);
        tr[p*2+1].data += tr[p].lztag * (tr[p*2+1].r - tr[p*2+1].l + 1);
        tr[p].lztag = 0;  // 清除当前节点的懒标记
    }
}
//点修改O(logn)
void pset(ll now, ll pos, ll addnum) {
    if (tr[now].l == tr[now].r) {
    	//点修改操作
        tr[now].data += addnum;
        return;
    }
    pushdown(now);  // 下传懒标记
    ll mid = (tr[now].l + tr[now].r) / 2;
    if (pos <= mid) pset(now*2, pos, addnum);
    else pset(now*2+1, pos, addnum);
    //合并操作
    tr[now].data = tr[now*2].data + tr[now*2+1].data;
}

//区间修改
void add(ll p, ll l, ll r, ll addnum) {
    if (tr[p].l >= l && tr[p].r <= r) {
        tr[p].lztag += addnum;  // 累加懒标记
        tr[p].data += addnum * (tr[p].r - tr[p].l + 1);  // 更新当前节点数据
        return;
    }
    pushdown(p);
    ll mid = (tr[p].l + tr[p].r) / 2;
    if (l <= mid) {
        add(2 * p, l, r, addnum);
    }
    if (r > mid) {
        add(2 * p + 1, l, r, addnum);
    }
    tr[p].data = tr[2 * p].data + tr[2 * p + 1].data;
}
//区间查询O(logn)
ll query(ll p, ll l, ll r) {
    if (l <= tr[p].l && r >= tr[p].r) {
        return tr[p].data;
    }
    pushdown(p);  // 处理懒标记
    ll mid = (tr[p].l + tr[p].r) / 2, sum = 0;
    if (l <= mid) sum += query(p*2, l, r);
    if (r > mid) sum += query(p*2+1, l, r);
    return sum;
}

int main(){
	ll n,m,temp,x,y,k;
	scanf("%lld%lld",&n,&m);
	for (ll i = 1; i <= n; ++i)
	{
		scanf("%lld",&data[i]);
	}
	segtreebuild(1,1,n);
	for (ll i = 0; i < m; ++i)
	{
		scanf("%lld",&temp);
		if(temp==1){
			scanf("%lld%lld%lld",&x,&y,&k);
			add(1,x,y,k);
		}else{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",query(1,x,y));
		}
	}
}