#35233: 範例


jasperlin0108@gmail.com (Jasper Lin)

學校 : 高雄市立高雄高級中學
編號 : 169403
來源 : [114.40.142.198]
最後登入時間 :
2023-10-05 16:52:06
d799. 区间求和 | From: [114.40.135.221] | 發表日期 : 2023-05-17 21:28

我變數名稱很奇怪,對不起。

#include <bits/stdc++.h>

using namespace std;

struct Node{
    long long val=0;
    long long add_val=0;
};

vector<long long> v;
vector<Node> tree;

long long build(int L,int R,int k){
    if(L==R){
        tree[k].val=v[L];
        return v[L];
    }
    tree[k].val=build(L,(L+R)/2,2*k)+build((L+R)/2+1,R,2*k+1);
    return tree[k].val;
}

long long query(int qL,int qR,int L,int R,int k){
    if(tree[k].add_val!=0){
        tree[2*k].add_val+=tree[k].add_val;
        tree[2*k+1].add_val+=tree[k].add_val;
        tree[k].val+=tree[k].add_val*(R-L+1);
        tree[k].add_val=0;
    }
    if(qL<=L && R<=qR){
        return tree[k].val;
    }
    if(R<qL || qR<L){
        return 0;
    }
    return query(qL,qR,L,(L+R)/2,2*k)+query(qL,qR,(L+R)/2+1,R,2*k+1);

}

void update(int qL,int qR,int L,int R,int k,long long add){
    if(tree[k].add_val!=0){
        tree[2*k].add_val+=tree[k].add_val;
        tree[2*k+1].add_val+=tree[k].add_val;
        tree[k].val+=tree[k].add_val*(R-L+1);
        tree[k].add_val=0;
    }
    if(qL<=L && R<=qR){
        tree[k].add_val=add;
        return;
    }
    if(R<qL || qR<L){
        return;
    }
    tree[k].val+=(min(qR,R)-max(qL,L)+1)*add;
    update(qL,qR,L,(L+R)/2,2*k,add);
    update(qL,qR,(L+R)/2+1,R,2*k+1,add);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    v.resize(n+5);
    tree.resize(4*n+5);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    build(1,n,1);
    int q;
    cin>>q;
    int v,x,y;
    long long z;
    for(int i=0;i<q;i++){
        cin>>v;
        if(v==2){
            cin>>x>>y;
            cout<<query(x,y,1,n,1)<<"\n";
        }
        if(v==1){
            cin>>x>>y>>z;
            update(x,y,1,n,1,z);
        }
    }
    return 0;
}

 
ZeroJudge Forum