[Algorithm] Baekjoon 2042번 : 구간 합 구하기

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

2042번: 구간 합 구하기

#define ll long long
 
ll arr[1000001];
ll segmentTree[4000005];
 
ll createSegmentTree(int start, int end, int node)
{
    if (start == end)
    {
        return segmentTree[node] = arr[start];
    }
 
    int mid = (start + end) / 2;
 
    return segmentTree[node] = createSegmentTree(start, mid, node * 2) + createSegmentTree(mid + 1, end, node * 2 + 1);
}
 
ll sum(int start, int end, int left, int right, int node)
{
    if (left > end || right < start) return 0;
 
    if (start >= left && end <= right)
    {
        return segmentTree[node];
    }
 
    int mid = (start + end) / 2;
 
    return sum(start, mid, left, right, node * 2) + sum(mid + 1, end, left, right, node * 2 + 1);
}
 
void update(int start, int end, int node, int index, ll num)
{
    if (index < start || index > end) return;
 
    segmentTree[node] += num;
 
    if (start == end) return;
 
    int mid = (start + end) / 2;
 
    update(start, mid, node * 2, index, num);
    update(mid + 1, end, node * 2 + 1, index, num);
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    ll n, m, k;
 
    cin >> n >> m >> k;
 
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    createSegmentTree(0, n - 1, 1); 
    vector<ll> result;
 
    for (int i = 0; i < m + k; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c; 
 
        if (a == 1) 
        {
            // b번째 수를 c로 변경
            ll num = c - arr[b - 1];
            arr[b - 1] = c;
            update(0, n - 1, 1, b-1, num);
        }
        else
        {
            // b번째부터 c번째값 합 출력.
            result.push_back(sum(0, n - 1, b - 1, c - 1, 1));
        }
    }
 
    for (int i = 0; i < result.size(); ++i)
    {
        printf("%lld\n", result[i]);
    }
 
    return 0;
}

세그먼트트리 기본예제 문제이다.

원래 구간합 구하기 4,5번을 푼다음, 좀 더 심화된 문제를 풀려고 이 문제로 왔던건데 4,5번과 달리 dp문제가 아니라 세그먼트트리 문제였다...  

아무리 생각해도 잘 모르겠어서 구글링했더니 아직 접해보지 못했던 세그먼트트리 문제라서 이기회에 공부해봤다.

이전에 이진트리같은걸 직접 코드로 짜봤다면 사실 그렇게 어렵지 않다. 아마 원리만 이해하면 의외로 코드로 작성하는건 금방 할 수 있을듯 하다.