[C/C++] 백준 #1275 커피숍2(세그먼트 트리)

#1275 커피숍2는 세그먼트 트리를 이용한 전형적인 문제입니다. 

 

문제 링크입니다.

https://www.acmicpc.net/problem/1275

1275번: 커피숍2

 

백준 알고리즘 문제들 중 어려운 문제들의 유형이 몇가지가 있는데, 이 문제는 그 중 세그먼트 트리 등 이진트리의 변형을 이용하고 있습니다.  비트 단위로 만들 수 있는 펜윅트리도 있고, 원한다면 자신만의 트리를 만들 수 있습니다.  일반적인 2진트리가 왼쪽과 오른쪽 링크를 연결하는 구조로 되어 있지만, 상기한 트리들은 인덱스에 의해서 자동으로 트리의 위치를 알 수 있습니다.  그렇기 때문에 링크를 저장하기 위한 별도의 구조가 필요하지 않고, 배열만을 이용합니다.  이런 점들은 힙과 비슷합니다.

 

coffee shop

 

N개의 데이터가 있는데, 이중 X에서 Y까지의 구간합을 표시해주어야 합니다.  가장 쉬운 방법은 1번째 데이터부터 K번째 데이터까지의 합을 저장하고 있으면 됩니다.  하지만, 이 문제에서는 그렇게 할 수 없도록 중간에 있는 데이터들을 변경합니다.  쉬운 방법을 이용해서 데이터를 저장한 방법을 사용했다면,

 

원데이터

1

2

3

4

5

첫번째 데이터부터의 합 데이터

1

3

6

10

15

세번째 데이터가 3에서 10으로 변경된 경우의 합 데이터

1

3

[13]

[17]

[22]

 

위와 같이 3개의 값을 변경하게 됩니다.

 

데이터의 갯수 N, 합을 표시하는 횟수 S, 데이터 변경횟수 K가 지정되어 있다면, 알고리즘 평가는,

\[ O(S + KN) \]

으로, K 값이 크다면, 이 부분이 주요한 알고리즘의 시간을 잡아먹게 됩니다.

 

이 문제에서는 10만회정도의 변경횟수가 있고 10만개정도의 데이터를 가지고 있는 문제이므로 100억 정도의 변경이 가해지므로 적절한 시간안에 처리하기가 힘듭니다.

 

그렇다고 합을 미리 저장하지 않고, 매번 구간합을 계산하는 것이라면,

\[ O(SN + K) \]

로 S 값이 크다면, 이것에 의해서 속도가 오래 걸리게 됩니다.

 

이 문제에서는 10만회정도의 구간합을 구하고 10만개정도의 데이터가 있습니다.

 

그래서 그 절충으로 구간합과 데이터 변경을 모두 이분하여 처리하도록 합니다.  그걸 가능하게 하는 자료구조가 세그먼트 트리와 같은 이진트리입니다.  이에 대해서는 별도로 한번 정리를 할께요.  이것을 이용하면,

\[ O( (S+K) \log N ) \]

으로 합을 구할 때, 데이터를 변경할 때, 모두 \( O( \log N ) \)의 복잡성을 가집니다.

 

이 문제와 같이 10만회정도의 변경횟수, 10만회정도의 합 출력, 10만개정도의 데이터라면, 340만 정도의 변경 및 합이 이루어집니다.  초기비용은 \(O(N)\)이므로 무시할만 합니다.  결국 이런 방법을 사용하지 않고는 이 문제를 해결할 수 없습니다.

 

Segment Tree

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #1275 - Coffee Shop 2
//        - by Aubrey Choi
//        - created at 2020-01-13
//----------------------------------------------------------
#include <stdio.h>

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

int main()
{
    int n, q, x, y, a, b;
    scanf("%d%d",&n,&q);
    SegmentTree tree(n);
    int *v = tree.getValue();
    for(int i=0;i<n;i++) scanf("%d", v+i);
    tree.init(1, 0, n);
    while(q--)
    {
        scanf("%d%d%d%d",&x,&y,&a,&b);
        if(x>y) { int t=x; x=y; y=t; }
        printf("%lld\n", tree.sum(1, 0, n, x-1, y));
        tree.update(1, 0, n, a-1, b);
    }
}