BOJ 2042번 구간 합 구하기

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

github : https://github.com/junho0956/Algorithm/blob/master/2042/2042/%EC%86%8C%EC%8A%A4.cpp

 

세그먼트트리를 이용하여 해결하였다.

 

세그먼트트리 정리 : https://junho0956.tistory.com/180

 

#include <iostream>
using namespace std;
 
typedef long long ll;
ll arr[1000004];
ll seg[3000004];
int n, m, k;
 
ll segment(int left, int right, int node) {
    if (left == right)
        return seg[node] = arr[left];
 
    int mid = (left + right) / 2;
    seg[node] += segment(left, mid, node * 2);
    seg[node] += segment(mid + 1, right, node * 2 + 1);
 
    return seg[node];
}
 
void update(int node, int left, int right, int change, int val) {
 
    if (!(left <= change && change <= right)) return;
 
    seg[node] += (val - arr[change]);
 
    if (left != right) {
        int mid = (left + right) / 2;
        update(node * 2, left, mid, change, val);
        update(node * 2 + 1, mid + 1, right, change, val);
    }
 
}
 
ll sum(int node, int left, int right, int s, int e) {
    if (left > e || right < s) return 0;
    if (s <= left && e >= right) return seg[node];
 
    int mid = (left + right) / 2;
    return sum(node * 2, left, mid, s, e) + sum(node * 2 + 1, mid + 1, right, s, e);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    seg[1] = segment(1, n, 1);
    int testcase = m + k;
    while (testcase--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) update(1, 1, n, b, c), arr[b] = c;
        else cout << sum(1, 1, n, b, c) << "\n";
    }
 
    return 0;
}