커피숍2


작성일 : 2017-02-05 18:24:28
조회수 : 694



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


특정 위치의 합을 구하거나 값을 변경하면서 그 결과를 매 쿼리마다 처리해 줄 때는 $O(N^2)$ 의 시간복잡도로 풀 수 없습니다. 그러므로 이러한 문제를 풀 때는 세그먼트 트리라는 개념을 사용합니다. 세그먼트 트리를 이미지로 표현하면 아래와 같습니다.



출처 : algorithmandme.in


분할 정복을 공부하셨다면 위의 개념을 이해할 수 있습니다. 루트가 전체라고 하면 좌측 subtree에는 왼쪽 절반, 우측 subtree에는 우측 절반을 저장합니다. 마찬가지로 나눠진 것에 대해 또 절반, 절반, ... 을 하며 구간의 합을 저장하는 자료 구조입니다. 이러한 자료구조를 이용할 경우 삽입, 갱신을 $O(logn)$ 의 시간복잡도로 할 수 있습니다.


커피숍2와 같은 문제는 펜윅 트리를 이용하여 더욱 쉽게 짤 수 있습니다. 하지만 여기 소스코드에는 정통(?) Segment Tree로 해결한 소스코드를 첨부하겠습니다.


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

ll init(vector<ll> &l, vector<ll> &tree, int node, int start, int end)
{
    if (start == end) return tree[node] = l[start];
    return tree[node] = init(l, tree, node * 2, start, (start + end) / 2) + init(l, tree, node * 2 + 1, (start + end) / 2 + 1, end);
}
ll sum(vector<ll> &tree, int node, int left, int right, int start, int end)
{
    if (left > end || right < start) return 0;
    if (left <= start && end <= right) return tree[node];
    
    return sum(tree, node * 2, left, right, start, (start+end)/2) + sum(tree, node * 2 + 1, left, right, (start+end)/2+1, end);
}
void update(vector<ll> &tree, int node, int idx, int start, int end, ll diff)
{
    if (idx < start || idx > end) return;
    tree[node] += diff;
    if (start != end)
    {
        update(tree, node * 2, idx, start, (start + end) / 2, diff);
        update(tree, node * 2 + 1, idx, (start + end) / 2 + 1, end, diff);
    }
}
int main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    int size = (int)ceil(log2(n));
    size = 1 << (size + 1);
    vector<ll> l(n), tree(size);

    for (int i = 0; i < n; i++) scanf("%lld", &l[i]);
    init(l, tree, 1, 0, n - 1);

    while(m--)
    {
        int x, y, z, w;
        
        scanf("%d %d %d %d", &x, &y, &z, &w);
        if (x > y) swap(x, y);
        if (x>=1 && x<=n && y>=1 && y<=n) printf("%lld\n", sum(tree, 1, x - 1, y - 1, 0, n - 1));
        if (z < 1 || z > n) continue;
        update(tree, 1, z - 1, 0, n - 1, w - l[z - 1]);
        l[z - 1] = w;
    }
}

커피숍2 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글