구간 합 구하기 (feat. 백준, 2042번)

구간 합 구하기
https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2042
#include using namespace std;
int N, M, K;
long long arr[1000001], tree[4000000];
long long sum_range(int L, int R, int node, int nodeL, int nodeR) {
    if (nodeL > R || nodeR < L) return 0;
    if (L <= nodeL && nodeR <= R) return tree[node];
    register int mid = (nodeL + nodeR) / 2;
    return sum_range(L, R, node * 2, nodeL, mid) + sum_range(L, R, node * 2 + 1, mid + 1, nodeR);
}
long long update_tree(int i, long long val, int node, int s, int e) {
    if (i < s || e < i) return tree[node];
    if (s == e) {
        tree[node] = val;
        return tree[node];
    }
    register int mid = (s + e) / 2;
    tree[node] = update_tree(i, val, node * 2, s, mid) + update_tree(i, val, node * 2 + 1, mid + 1, e);
    return tree[node];
}
long long make_tree(int node, int s, int e) {
    if (s == e) {
        tree[node] = arr[s];
        return tree[node];
    }
    register int mid = (s + e) / 2;
    tree[node] = make_tree(node * 2, s, mid) + make_tree(node * 2 + 1, mid + 1, e); return tree[node];
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> M >> K;
    for (register int i = 1; i <= N; ++i)
        cin >> arr[i];
    make_tree(1, 1, N);
    register long long c;
    for (register int i = 0, a, b; i < M + K; ++i) {
        cin >> a >> b >> c;
        if (a == 1)
            update_tree(b, c, 1, 1, N);
        else if (a == 2)
            cout << sum_range(b, c, 1, 1, N) << "\n";
    }
    return 0;
}
// *&)*@*

처음 풀어본 세그먼트 트리 알고리즘 이었습니다.

세그먼트 트리를 만드는 방식 (코드 내 make_tree) 는 외워보는 것도 좋을 것 같습니다.

세그먼트 트리에 대해 설명이 잘 되어 있는 링크를 걸어둡니다.

41. 세그먼트 트리(Segment Tree)