[C/C++] 백준 #2042 구간 합 구하기(세그먼트 트리)

구간 합 구하기 문제는 전형적인 세그먼트 트리를 이용하여 푸는 문제입니다.  세그먼트 트리 이외에도 비슷한 방식들이 존재합니다.

세그먼트 트리를 이용하는 문제는,

 

1. 많은 수의 쿼리를 진행해야 하고,

2. 미리 연산한 결과를 사용할 수 있어야 하고,

3. 미리 연산한 결과를 수정해야할 경우가 많은 경우

 

형태일겁니다.

 

위의 조건이 만족하지 않는다면, 다른 방식으로 계산하는 것이 더 좋을 수 있습니다.

 

세그먼트 트리와 관련한 문제들은 다음과 같습니다.

 

https://sdev.tistory.com/958

백준 #1849 순열(세그먼트 트리)

 

https://sdev.tistory.com/598

#1395 스위치(Segment Tree)

 

https://sdev.tistory.com/512

백준 #1275 커피숍2

 

세그먼트 트리는 $O((S+K)\log N)$ 형태의 알고리즘입니다.  웬만한 N에 대해서 $O(\log N)$은 상당히 작은 값이기 때문에 효율적으로 사용할 수 있습니다.

 

Segment Tree

 

다음은 제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2042
//        - by Aubrey Choi
//        - created at 2019-08-04
//------------------------------------------------
#include <stdio.h>

//    Segment tree
template<class T> class SegmentTree
{
public:
    SegmentTree(int n) { int s=1; while(s<n) s<<=1; tree = new T[s<<1]; v = new T[n]; }
    ~SegmentTree() { delete[] tree; delete[] v; }
    T init(int c, int s, int e)
    {
        if(s+1==e) return tree[c]=v[s];
        int m = (s+e)/2;
        return tree[c]=init(c*2, s, m)+init(c*2+1, m, e);
    }
    void update(int c, int s, int e, int idx, T diff)
    {
        if(idx<s||idx>=e) return;
        tree[c]+=diff;
        if(s+1==e) return;
        int m = (s+e)/2;
        update(c*2, s, m, idx, diff);
        update(c*2+1, m, e, idx, diff);
    }
    int find(int c, int s, int e, T sum)
    {
        if(s+1==e) return s;
        int m = (s+e)/2;
        if(tree[c*2]>=sum) return find(c*2, s, m, sum);
        return find(c*2+1, m, e, sum-tree[c*2]);
    }
    T sum(int c, int s, int e, int sc, int ec)
    {
        if(ec<=s||sc>=e) return 0; if(sc<=s&&ec>=e) return tree[c];
        int m = (s+e)/2;
        return sum(c*2,s,m,sc,ec)+sum(c*2+1,m,e,sc,ec);
    }
    T operator [](const int i) { return v[i]; }
    T *getTree() { return tree+1; }
    T *getValue() { return v; }
private:
    T *tree, *v;
};

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k); m+=k;
    SegmentTree<long long> tree(n);
    long long *data = tree.getValue();
    for(int i=0;i<n;i++) scanf("%lld",data+i);
    tree.init(1,0,n);
    while(m--)
    {
        int a, b; long long c;
        scanf("%d%d%lld", &a, &b, &c);
        if(a==1) { c-=data[b-1]; data[b-1]+=c; tree.update(1, 0, n, b-1, c); }
        else printf("%lld\n", tree.sum(1, 0, n, b-1, (int)c));
    }
    return 0;
}