BOJ 02042(구간 합 구하기) 문제 풀이

목차

• 참조
• 개요
  • 시간복잡도: $ O(N + (k+m)log N) $
  • 공간복잡도: $ O(N) $
• 문제 풀이
• 구현

참조

개요

시간복잡도: $ O(N + (k+m)log N) $

공간복잡도: $ O(N) $

• N, m, k는 문제에서 주어진 그대로이다. N은 원소의 수이다.

문제 풀이

이 문제는 흔히 인덱스 트리라고 부르는 자료구조를 써도 풀리지만, 펜윅 트리가 굉장히 간단하기 때문에 이것으로 문제를 풀었다.

원소가 하나씩 업데이트될 때, 구간의 합을 구하라는 문제는 그냥 펜윅 트리를 쓰라는 문제이다. 왜냐하면 BIT가 그에 최적화되어 있기 때문이다.

본인이 인덱스 트리를 좋아한다면 그것으로 풀어도 상관없지만, 코딩하기 조오금 더 귀찮지 않은가?

별다른 풀이는 없다. 그냥 펜윅 트리를 쓴다. 그게 끝이다.

구현

• 참고로 m과 k의 구분은 전혀 필요가 없다. 그냥 합쳐서 생각하면 된다.
• 펜윅 트리 클래스의 구현을 보면 data[]에는 long long을 쓴다. 합이 int의 범위를 넘어가기 때문이다. 제출했는데 초반은 맞다가 갑자기 틀린다면, 오버플로우를 한번쯤 의심해 봐야 한다.

#include "../library/sharifa_header.h"
#include "../library/Fenwick_tree_BIT.h"

int N, m, k;

int main_02042() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);    cin.tie(NULL);

    cin >> N >> m >> k;
    m += k;

    FenwickTree<int> BIT(N);

    int a, b, c;

    for (int i = 1; i <= N; i++) {
        cin >> c;
        BIT.update(i, c);
    }

    while (m--) {
        cin >> a >> b >> c;
        if (a == 1)
            BIT.update(b, c);
        else
            cout << BIT.sum(b, c) << '\n';
    }
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있을까?