静态线段树（动态开点的后边再补
#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)); } } }