[c++][백준 2042] 구간 합 구하기

백준 2042번: 구간 합 구하기 [Gold 1]
https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

문제 풀이

• 이 문제는 구간 합을 구하는 문제로 단순하게 n ~ m을 반복문을 통해 더하게 되면 시간 초과에 걸리게 됩니다.
• 구간 합을 위해 세그먼트 트리나 펜윅 트리를 구현해야 하는데, 저는 펜윅 트리를 구현하여 문제를 풀었습니다.
• 아래의 링크에 세그먼트 트리와 펜윅 트리의 개념에 대해 잘 설명되어 있어서 개념을 숙지해 두시면 좋을 것 같습니다!
• 펜윅 트리 : https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

• 세그먼트 트리 : https://www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

코드

#include <vector>
#include <cstdio>

using namespace std;

typedef long long ll;
int N, M, K;

void update(vector<ll> &fen_tree, int idx, ll diff) {
    while(idx < N+1) {
        fen_tree[idx] += diff;
        idx += (idx & -idx);
    }
}

ll sum(vector<ll> &fen_tree, int idx) {
    ll ret = 0;
    while(idx > 0) {
        ret += fen_tree[idx];
        idx -= (idx & -idx);
    }

    return ret;
}

int main() {
    scanf("%d %d %d", &N, &M, &K);
    
    vector<ll> arr(N+1);
    vector<ll> fen_tree(N+1);

    for(int i=1; i<=N; ++i) {
        scanf("%lld", &arr[i]);
        update(fen_tree, i, arr[i]);
    }

    for(int i=0; i<M+K; ++i) {
        int a;
        scanf("%d", &a);

        if(a == 1) {
            int b;
            ll c;
            scanf("%d %lld", &b, &c);

            ll diff = c - arr[b];
            arr[b] = c;
            update(fen_tree, b, diff);
        }
        else {
            int b, c;
            scanf("%d %d", &b, &c);
            ll res = sum(fen_tree, c) - sum(fen_tree, b-1);
            printf("%lld\n", res);       
        }
    }    

    return 0;
}

실행 결과