Bottom-Up Segment Tree

2042번: 구간 합 구하기

 

#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
struct Segment {
    vector<ll> tree; int n;
    Segment(int n) : tree(2*n), n(n) {}
    ll f(ll a,ll b) {
        return a+b;
    }
    void init() {
        for(int i=n-1;i>0;i--) tree[i]=f(tree[i<<1],tree[i<<1|1]);
    }
    void update(int i,ll val) {
        for(tree[i+=n]=val;i>1;i>>=1) tree[i>>1]=f(tree[i],tree[i^1]);
    }
    ll query(int l,int r) {
        ll res=0; // 기본값
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1) res=f(res,tree[l++]);
            if(!(r&1)) res=f(res,tree[r--]);
        }
        return res;
    }
};
int main()
{
    fastio;
    int n,m,k;
    cin >> n >> m >> k;
    Segment seg(n);
    for(int i=0;i<n;i++) cin >> seg.tree[n+i];
    seg.init();
    for(m+=k;m--;){
        int t; cin >> t;
        if(t==1){
            int i; ll val;
            cin >> i >> val;
            seg.update(i-1,val);
        }
        else{
            int l,r;
            cin >> l >> r;
            cout << seg.query(l-1,r-1)<< '\n';
        }
    }
}