懶蛋線段樹.cpp

//支援該死的懶人標記，看學長的講義結果他講義是錯的啊在幹嘛
//害我一直debug 真是可惡

#include <iostream>
#include <string.h>
#include <stdio.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define N 500005
#define int long long
using namespace std;
int seg[4*N],arr[N],lazy[4*N],n,m;

void init(){
    memset(seg,0,sizeof(seg));
    memset(lazy,0,sizeof(lazy));
    memset(arr,0,sizeof(arr));
}

void build(int l,int r,int cur){
    if(r<=l)return;
    if(r-l==1){
        seg[cur] = arr[l];
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*cur);
    build(m,r,2*cur+1);
    seg[cur] = seg[2*cur]+seg[2*cur+1];
}

//把id的懶標在query的時候往下推
void push(int id,int size){
    lazy[2*id] += lazy[id];
    lazy[2*id+1] += lazy[id];
    seg[id] += lazy[id]*size;
    lazy[id] = 0;
}

//區間修改
void modify(int cur,int l,int r,int ql,int qr,int val){
    if (r<=l||ql>=r||qr<=l)return;
    if (ql<=l && qr>=r) {
        lazy[cur]+=val;
        return;
    }
    int mid = (l+r)/2;
    modify(cur*2,l,mid,ql,qr,val);
    modify(cur*2+1,mid,r,ql,qr,val);
    seg[cur] = seg[cur*2]+(mid-l)*lazy[cur*2]+seg[cur*2+1]+(r-mid)*lazy[cur*2+1];
}

//區間詢問
int query(int cur,int l,int r,int ql,int qr){
    if(r<=l || ql>=r || qr<=l)return 0;
    if(ql<=l && qr>=r)return seg[cur]+(r-l)*lazy[cur];
    push(cur,r-l);
    int mid = (l+r)/2;
    return query(cur*2,l,mid,ql,qr)+query(cur*2+1,mid,r,ql,qr);
}

signed main(){
    ios;
    init();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr[i];
    build(1,n+1,1);
    cin>>m;
    
    while(m--){
        int p;cin>>p;
        if(p==1){
            int x,y,k;cin>>x>>y>>k;
            modify(1,1,n+1,x,y+1,k);
        }
        else if(p==2){
            int x,y;cin>>x>>y;
            int ans = query(1,1,n+1,x,y+1);
            cout<<ans<<endl;
        }
//        for(int i=1;i<=n<<2;i++)cout<<seg[i]<<" ";
//        cout<<endl;
//        for(int i=1;i<=n<<2;i++)cout<<lazy[i]<<" ";
//        cout<<endl;
    }
}