#32232: 線段樹 C++程式碼


zaqxswdce26@gmail.com (卡比獸)

學校 : 不指定學校
編號 : 192970
來源 : [49.216.222.215]
最後登入時間 :
2023-10-24 13:17:05
d799. 区间求和 | From: [220.141.66.89] | 發表日期 : 2022-09-23 23:02

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,int> > smt;// 區間data /  val,暫時用來表示這個節點的區間每個元素的值都要加上val
vector<int> data;
int n;
void create(int idx,int l,int r)
{
    if(l!=r)
    {
        create(idx*2+1,l,(l+r)/2);
        create(idx*2+2,(l+r)/2+1,r);
        smt[idx].first=smt[idx*2+1].first+smt[idx*2+2].first;
    }
    else
        smt[idx].first=data[l];
}
long long search(int idx,int l,int r,int sl,int sr)
{
    if(sl==l && sr==r)
        return smt[idx].first+(r-l+1)*smt[idx].second;
    if(smt[idx].second>0)
    {
        smt[idx*2+1].second+=smt[idx].second;
        smt[idx*2+2].second+=smt[idx].second;
        smt[idx].first+=(r-l+1)*smt[idx].second;
        smt[idx].second=0;
    }
    if(sr<=(l+r)/2)
        return search(idx*2+1,l,(l+r)/2,sl,sr);
    if(sl>(l+r)/2)
        return search(idx*2+2,(l+r)/2+1,r,sl,sr);
    return search(idx*2+1,l,(l+r)/2,sl,(l+r)/2)+search(idx*2+2,(l+r)/2+1,r,(l+r)/2+1,sr);
}

void addr(int idx,int l,int r,int sl,int sr,int add)
{//要做查詢區間[sl,sr]的動作,然還沒找到這個區間之前都可以把走訪到的區間做add的動作來在當下走訪的節點獲得正確的區間總和

//當走訪到區間[sl,sr]時,把表示[sl,sr]的節點時,為了節省時間(不然如果把[sl,sr]的全部兒子都處理完會太久)我們暫時把每個元素要加的值存放到smt[idx].second(val)。在之後做search()時,如果有走訪到這個節點,並且需要繼續往下走,在這時才有必要把這個節點目前正確的值用smt[idx].second跟smt[idx].first算出來,並把這個節點的兒子的val都加上smt[idx].second再把這個節點的val重設為0,之後繼續往下尋找需要的區間並同時做處理,直到我們找到需要的區間為止
    if(sl==l && sr==r)
    { 
        smt[idx].second+=add;
        return;
    }
    if(sr<=(l+r)/2)
    { 
        addr(idx*2+1,l,(l+r)/2,sl,sr,add);
        smt[idx].first+=(sr-sl+1)*add;
        return;
    } 
    if(sl>(l+r)/2)
    { 
        addr(idx*2+2,(l+r)/2+1,r,sl,sr,add);
        smt[idx].first+=(sr-sl+1)*add;
        return;
    } 
    addr(idx*2+1,l,(l+r)/2,sl,(l+r)/2,add);
    addr(idx*2+2,(l+r)/2+1,r,(l+r)/2+1,sr,add);
    smt[idx].first+=(sr-sl+1)*add;
}
int main(void)
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int a,b,c,d,e,f;
    cin>>n;
    data.resize(n);
    smt.resize(n*4);
    for(a=0;a<n;a++)
        cin>>data[a];
    create(0,0,n-1);
    cin>>f;
    for(a=0;a<f;a++)
    {
        cin>>b;
        if(b==1)
        {
            cin>>c>>d>>e;
            addr(0,0,n-1,c-1,d-1,e);
        }
        else
        {
            cin>>c>>d;
            cout<<search(0,0,n-1,c-1,d-1)<<"\n";
        }
    }

    return 0;
}

 
ZeroJudge Forum