BOJ 2042 구간 합 구하기

1 개요

BOJ 2042 구간 합 구하기

• 백준 온라인 저지 2042번 문제
• BOJ 45단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N, M, K;
vector<long long> numbers;
vector<long long> tree;

void init() {
    for (int i = N - 1; i > 0; --i) {
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
}

long long sum(int l, int r) {
    long long res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res += tree[l++];
        if (r & 1) res += tree[--r];
    }
    return res;
}

void update(int pos, long long value) {
    for (tree[pos += N] = value; pos > 1; pos >>= 1) {
        tree[pos >> 1] = tree[pos] + tree[pos ^ 1];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;
    numbers.resize(N);
    tree.resize(2 * N);
    for (int i = 0; i < N; i++) {
        cin >> numbers[i];
        tree[N + i] = numbers[i];
    }
    init();
    int a, b;
    long long c;
    for (int i = 0; i < M + K; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            update(b - 1, c);
        } else {
            cout << sum(b - 1, c) << '\n';
        }
    }
}