백준[2042] 구간 합 구하기

문제 설명

문제 링크

http://icpc.me/2042

2042번: 구간 합 구하기

풀이

세그먼트 트리 또는 펜윅 트리 기본 문제이다.

개념을 설명은 다른 분이 잘해놓으셔서 생략하겠다.

세그먼트 트리는 여기를 펜윅트리는 여기를 참고해라.

코드

세그먼트 트리

#include <cstdio>

using ll = long long;

ll arr[1000006];
ll tree[4000006];

ll init(ll node, ll start, ll end) {
    if (start == end) return tree[node] = arr[start];
    ll mid = (start + end) / 2;
    ll left = init(node * 2, start, mid);
    ll right = init(node * 2 + 1, mid + 1, end);
    return tree[node] = left + right;
}

ll sum(ll node, ll start, ll end, ll left, ll right) {
    if (start > right || end < left) return 0;
    if (left <= start && end <= right) return tree[node];
    ll mid = (start + end) / 2;
    return sum(node * 2, start, mid, left, right) + sum(node * 2 + 1, mid + 1, end, left, right);
}

void update(ll start, ll end, ll node, ll index, ll dif) {
    if (index < start || index > end) return;
    tree[node] += dif;
    if (start == end) return;
    ll mid = (start + end) / 2;
    update(start, mid, node * 2, index, dif);
    update(mid + 1, end, node * 2 + 1, index, dif);
}

int main() {
    ll N, M, K; scanf("%lld %lld %lld", &N, &M, &K);
    for (ll i = 0; i < N; i++)
        scanf("%lld", arr + i);
    init(1, 0, N - 1);
    for (ll i = 0; i < M + K; i++) {
        ll a, b, c; scanf("%lld %lld %lld", &a, &b, &c);
        if (a == 1) {
            ll dif = c - arr[b - 1];
            arr[b - 1] = c;
            update(0, N - 1, 1, b - 1, dif);
        } else {
            printf("%lld\n", sum(1, 0, N - 1, b - 1, c - 1));
        }
    }
}

펜윅트리

#include <cstdio>
#include <cstring>

using ll = long long;

struct Fenwick {
    Fenwick(ll size) : size(size) { memset(tree, 0, sizeof tree); }
    ll tree[1000006], size;
    void update(ll i, ll diff) {
        while (i < size) {
            tree[i] += diff;
            i += (i & -i);
        }
    }
    ll query(ll i) {
        ll ret = 0;
        while (i > 0) {
            ret += tree[i];
            i -= (i & -i);
        }
        return ret;
    }
};

ll arr[1000006];

int main() {
    ll n, m, k; scanf("%lld %lld %lld", &n, &m, &k);
    Fenwick fenwick = Fenwick(n + 1);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", arr + i);
        fenwick.update(i, arr[i]);
    }
    ll q = m + k;
    while (q--) {
        ll k, a, b; scanf("%lld %lld %lld", &k, &a, &b);
        if (k == 1) {
            fenwick.update(a, b - arr[a]);
            arr[a] = b;
        } else {
            printf("%lld\n", fenwick.query(b) - fenwick.query(a - 1));
        }
    }
}