백준 2042번: 구간 합 구하기 (C++)

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

2042번: 구간 합 구하기

---

Solved By: Segment Tree

 

저번에도 포스팅했던 문제이지만 세그트리 관련 문제를 푼 지가 오래되어서 다시 풀어보았습니다. 구성은 다행히 기억하고 있더군요. 다만 원래 배열 값에도 업데이트를 하지 않아서 맞왜틀을 시전하고 있었습니다...ㅎ

#include <iostream>
#define MAX 1000001
#define ll long long
using namespace std;

int n, m, k;
ll arr[MAX];
ll sgTree[4 * MAX];

void sgInit(int node, int left, int right){
    if(left == right){
        sgTree[node] = arr[left];
        return;
    }
    
    int mid = (left + right) >> 1;
    sgInit(node * 2, left, mid);
    sgInit(node * 2 + 1, mid + 1, right);
    sgTree[node] = sgTree[node * 2] + sgTree[node * 2 + 1];
}

void update(int node, int left, int right, int idx, ll value){
    if(idx < left || idx > right) return;
    
    sgTree[node] += value;
    if(left == right) return; // leaf node에서 끝내기
    
    int mid = (left + right) >> 1;
    update(node * 2, left, mid, idx, value);
    update(node * 2 + 1, mid + 1, right, idx, value);
}

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    
    sgInit(1, 1, n);
    
    for(int i = 0; i < m + k; i++){
        int a, b; ll c;
        cin >> a >> b >> c;
        if(a == 1){
            ll diff = c - arr[b];
            arr[b] = c;
            update(1, 1, n, b, diff);
        }
        else{
            cout << query(1, 1, n, b, c) << '\n';
        }
    }
}