新概念线段树 10披头士 求调

RT.

query 只涉及 O(logn) 个区间，rt.sum 表示不考虑那些涉及 rt 上级的修改后区间 rt 内各数总和，rt.add 表示那些涉及 rt 的修改里 k 的总和。

最后 ans=rt.sum+ (从树根到 rt 一路上的 add 总和)。

代码：

#include<bits/stdc++.h>
#define lc(x) tr[x.l]
#define rc(x) tr[x.r]
using namespace std;
const int N=100005;
typedef long long ll;
int n,m; 
int a[N];
struct Node{
    int l,r,len;
    ll add,sum;
} tr[N<<2];
void pushup(Node &rt){
    rt.sum=lc(rt).sum+rc(rt).sum;
}
void build(int rt,int l,int r){
    tr[rt].len=r-l+1;
    if(l==r){tr[rt].sum=a[l];return;}
    int mid=l+r>>1;
    tr[rt].l=rt<<1;
    tr[rt].r=rt<<1|1;
    build(tr[rt].l,l,mid);
    build(tr[rt].r,mid+1,r);
    pushup(tr[rt]);
}
void update(Node &rt,int l,int r,int a,int b,int c){
    if(a<=l&&b>=r){rt.add+=c;rt.sum+=(ll)c*rt.len;return;}
    int mid=l+r>>1;
    if(a<=mid) update(lc(rt),l,mid,a,b,c);
    if(b>mid) update(rc(rt),mid+1,r,a,b,c);
    pushup(rt);
}
ll query(Node &rt,int l,int r,int a,int b,ll s){
    if(a<=l&&b>=r) return s*rt.len+rt.sum;
    int mid=l+r>>1;
    ll ans=0;
    if(a<=mid) ans+=query(lc(rt),l,mid,a,b,s+rt.add);
    if(b>mid) ans+=query(rc(rt),mid+1,r,a,b,s+rt.add);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        int op;scanf("%d",&op);
        if(op==1){
            int l,r,k;scanf("%d%d%d",&l,&r,&k);
            update(tr[1],1,n,l,r,k);
        }else{
            int l,r;scanf("%d%d",&l,&r);
            printf("%lld\n",query(tr[1],1,n,l,r,0));
        }
        //cout<<"sum:"<<tr[1].sum<<endl;
    }
    return 0;
}