본문 바로가기

Algorithm/Data structure

Bottom-Up Segment Tree

 

2042번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

#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';
        }
    }
}

'Algorithm > Data structure' 카테고리의 다른 글

경로 가중치 합 hld 구현 코드  (0) 2021.07.06
Segment Tree and Lazy Propagation  (0) 2021.05.28
연속합 최대 Segment Tree  (2) 2021.05.22
Li Chao Tree  (2) 2021.05.18
Bottom-Up Segment Tree  (2) 2021.04.18
Fenwick Tree  (4) 2021.04.04