2042 구간 합 구하기

BOJ::2042 구간 합 구하기

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

세그먼트 트리 혹은 바이너리트리를 활용해 푸는 문제이다.

앞의 자료구조를 알기전 혼자 여러가지 방법으로 풀어보았으나 모두 실패하였고,

https://www.acmicpc.net/blog/view/9와 https://www.acmicpc.net/blog/view/21 를 참고하여 세그먼트 트리 및 펜윅트리에 대해 공부를 해보았다.

아직 잘 이해가 안되므로 여러번 풀어보아야 할 것 같다.

<세그먼트 트리>

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
 
LL init(vector<LL> &a, vector<LL> &tree, int node, int start, int end) {
    if (start == end) {
        return tree[node] = a[start];
    }
    else {
        return tree[node] = init(a, tree, node * 2, start, (start + end) / 2) +
        init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end);
    }
}
 
void update(vector<LL> &tree, int node, int start, int end, int index, LL diff) {
    if (index < start || index > end) return;
    tree[node] = tree[node] + diff;
    if (start != end) {
        update(tree, node * 2, start, (start + end) / 2, index, diff);
        update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
    }
}
 
LL sum(vector<LL> &tree, int node,int start,int end,int left,int right) {
    if (left > end || right < start) {
        return 0;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    return sum(tree, node * 2, start, (start + end) / 2, left, right) +
        sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
}
 
int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector <LL> a(n);
    int h = (int)ceil(log2(n));
    vector<LL> tree((1 << h + 1));
    m += k;
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
 
    //트리 만들기
    init(a, tree, 1, 0, n - 1);
 
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d %d %d",&x,&y,&z);
        if (x == 1) {
            y--;
            long long diff = z - a[y];
            a[y] = z;
            update(tree, 1, 0, n - 1, y, diff);
        }
        else {
            printf("%lld\n", sum(tree, 1, 0, n - 1, y - 1, z - 1));
        }
    }
    return 0;
}

<펜윅 트리>

#include <cstdio>
#include <vector>
using namespace std;
 
long long sum(vector<long long> &tree, int i) {
    long long ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= (i & -i);
    }
    return ans;
}
 
void update(vector<long long> &tree, int i, int diff) {
    while (i <= tree.size()) {
        tree[i] += diff;
        i += (i&-i);
    }
}
 
int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector <long long> a(n + 1);
    vector <long long>tree(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        update(tree, i, a[i]);
    }
    m += k;
    while (m--) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        if (x == 1) {
            long long diff = z - a[y];
            a[y] = z;
            update(tree, y, diff);
        }
        else {
            printf("%lld\n", sum(tree, z) - sum(tree, y - 1));
        }
 
    }
 
 
    return 0;
}