[ 백준 11659 ] 구간 합 구하기 (C++, 세그먼트 트리)

[문제보기]

 

[해결과정]

 - 세그먼트 트리 사용

 

[소스코드]

typedef long long ll;
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

ll node[400000];
ll tree[400000];

// init(배열, 위치, 시작, 끝)
ll init(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR){
    if(dataIdxL == dataIdxR) return tree[treeIdx] = arr[dataIdxL-1];
    
    ll mid = (dataIdxL + dataIdxR) / 2;
    
    return tree[treeIdx] = init(arr, 2*treeIdx, dataIdxL, mid) + init(arr, 2*treeIdx+1, mid+1, dataIdxR);
}

// update(바꿀위치, 바꿀값, 위치, 시작, 끝)
ll update(ll dataIdx, ll value, ll treeIdx, ll dataIdxL, ll dataIdxR){
    if(dataIdxL > dataIdx || dataIdx > dataIdxR) return tree[treeIdx];
    if(dataIdxL == dataIdxR) return tree[treeIdx] = value;
    
    ll mid = (dataIdxL+dataIdxR) /2;
    return tree[treeIdx] = update(dataIdx, value, 2*treeIdx, dataIdxL, mid) + update(dataIdx, value, 2*treeIdx+1, mid+1, dataIdxR);
}

// query(시작위치, 끝위치, 위치, 시작, 끝)
ll query(ll queryL, ll queryR, ll treeIdx, ll dataIdxL, ll dataIdxR){
    if(queryL > dataIdxR || dataIdxL > queryR) return 0;
    if(dataIdxL >= queryL && queryR >= dataIdxR) return tree[treeIdx];
    
    ll mid = (dataIdxL + dataIdxR) / 2;
    return query(queryL, queryR, 2*treeIdx, dataIdxL, mid) + query(queryL, queryR, 2*treeIdx+1, mid+1, dataIdxR);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    ll n, m;
    cin >> n >> m;
    
    for(int i =0; i<n; i++) cin >> node[i];
    
    init(node, 1, 1, n);
    
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        
        cout << query(a, b, 1, 1, n)<< "\n";
    }
    
    
    
    return 0;
}

 

 

[해결 과정 중 실수한 부분 / 잡담]

 세그먼트 트리 문제를 풀기 위해서 세그먼트 트리 기본 3가지 (init, update, query) 소스 코드를 이해하고 작성하는데 많은 노력이 필요했다...

 

[관련 문제 혹은 비슷한 문제]

 구간 합 구하기