[2042] 구간 합 구하기

세그먼트 트리 OR 펜윅 트리로 해결할 수 있는 문제입니다.

세그먼트 트리랑 펜윅 트리 설명 글은 따로 준비해보겠습니다.

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

펜윅트리 : https://www.acmicpc.net/blog/view/21

boj 블로그에 있는 내용입니다.

참고하세요!

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
#define INF 0x7fffffff
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[(int)1e6 + 1];
ll tree[(int)1e6 + 1];
 
void update(int idx, int diff, int size) {
    while (idx <= size) {
        tree[idx] += diff;
        idx += (idx & -idx);
    }
}
 
ll sum(int idx) {
    ll ret = 0;
    while (idx) {
        ret += tree[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
 
    //트리를 만드는 과정
    for (int i = 1; i <= n; i++) {
        update(i, arr[i], n);
    }
 
    for (int i = 0; i < m + k; i++) {
        int cmd, a, b;
        cin >> cmd >> a >> b;
 
        if (cmd == 1) {
            update(a, b - arr[a], n);
            arr[a] = b;
        }
        else {
            cout << sum(b) - sum(a - 1) << '\n';
        }
    }
 
    return 0;
}