BOJ 2042 - 구간 합 구하기

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

2042번: 구간 합 구하기

 

세그먼트 트리를 이용한 문제.

 

세그먼트 트리는 배열 같이 연속적인 데이터가 주어졌을 때, 일부 구간 마다의 합을 구해서 트리로 표현하는 자료구조다.

 

http://arkainoh.blogspot.com/2018/06/segment.tree.html

[Algorithm] 세그먼트 트리 (Segment Tree)

 

원래 세그먼트 트리에 대해서

그림도 직접 그리고 설명도 다 쓰려고 했지만,

그럴때마다 글 하나하나 포스팅 하는게 시간이 너무 오래걸려서

아주 잘 설명되어 있는 위 블로그 글을 참조하는게 빠른것 같다.

 

이 문제를 풀때, 재귀 방식인 Top-Down Approach 로 문제를 풀었다.

 

- c++

#include <iostream>
 
typedef long long ll;
using namespace std;
 
int N, M, K;  // N 은 총 입력될 수의 갯수, M 은 변경이 일어나는 횟수, K 는 구간의 합을 구하는 횟수 이다.
 
// 구간 합 트리 초기화 함수
ll build_tree(ll* arr, ll* tree, ll node, ll start, ll end) {
    if (start == end) return tree[node] = arr[start];
 
    ll mid = (start + end) / 2;
    return tree[node] = build_tree(arr, tree, node * 2, start, mid) + build_tree(arr, tree, node * 2 + 1, mid + 1, end);
}
 
// 구간 합 트리 데이터 수정 함수
void update(ll* tree, ll node, ll start, ll end, ll index, ll data) {
    if (index > end || index < start) return;
 
    tree[node] += data;
 
    if (start == end) return;
 
    ll mid = (start + end) / 2;
    update(tree, node * 2, start, mid, index, data);
    update(tree, node * 2 + 1, mid + 1, end, index, data);
}
 
// 구간 합 트리 데이터 조회 함수
ll query(ll* tree, ll node, ll start, ll end, ll L, ll R) {
    if (L <= start && R >= end)
        return tree[node];
    else if (R < start || L > end)
        return 0;
    else {
        ll mid = (start + end) / 2;
        return query(tree, node * 2, start, mid, L, R) + query(tree, node * 2 + 1, mid + 1, end, L, R);
    }
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    cin >> N >> M >> K;
 
    ll* arr = new ll[N];
    ll* tree = new ll[4 * N];
 
    arr[0] = 0;
    tree[0] = 0;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    build_tree(arr, tree, 1, 1, N);
 
    ll a, b, c;
    for (int i = 0; i < M + K; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            // update 함수를 수행
            ll data = c - arr[b];
            update(tree, 1, 1, N, b, data);
            arr[b] += data;
        } else if (a == 2) {
            // query 함수를 수행
            cout << query(tree, 1, 1, N, b, c) << '\n';
        }
    }
 
    //delete[] tree;
    //delete[] arr;
    return 0;
}

 

 

 

왜 저런지는 아직도 잘 모르겠지만

동적할당을 해제하는 delete[] 구문을 사용하면 런타임 에러가 뜬다.

 

 

확실히 solved.ac 기준 플레티넘 이상의 문제들은

개념 이해하는데만 꽤 오랜 시간이 걸린것같다.

이문제도 그렇고..