[BOJ] 백준 2042 구간 합 구하기

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

 Input 
　 

 Output 

　

구간합을 처리하는 코드는 아래와 같이 구현할 수 있습니다.

하지만 배열 원소값을 변경과 구간 합을 구하는 것이

여러번 일어나기 때문에 이에 대한 효율적인 처리가 필요합니다.

세그먼트 트리(Segment Tree)

---

#include <iostream>
#include <vector>
#include <cmath>
typedef long long ll;
using namespace std;
 
int N, M, K;
vector<ll> arr, tree;
vector<pair<int, pair<int, ll>>> cmdList;
 
void input() {
    int i, a, b, c;
    cin >> N >> M >> K;
    for (i = 0; i < N; i++)
    {
        cin >> a;
        arr.push_back(a);
    }
    for (int i = 0; i < M + K; i++)
    {
        cin >> a >> b >> c;
        cmdList.push_back(make_pair(a, make_pair(b, c)));
    }
}
 
ll Make_SegmentTree(int node, int start, int end)
{
    // 단말(leaf) 노드
    if (start == end)
        return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
    ll L = Make_SegmentTree(node * 2, start, mid);
    ll R = Make_SegmentTree(node * 2 + 1, mid + 1, end);
    tree[node] = L + R;
    return tree[node];
}
 
void Query_Update_SegmentTree(int node, int start, int end, int idx, ll diff)
{
    if (idx < start || idx > end) return;
    tree[node] = tree[node] + diff;
 
    if (start != end)
    {
        int mid = (start + end) / 2;
        Query_Update_SegmentTree(node * 2, start, mid, idx, diff);
        Query_Update_SegmentTree(node * 2 + 1, mid + 1, end, idx, diff);
    }
}
 
ll Query_Sum_SegmentTree(int node, int start, int end, int left, int right)
{
    if (left > end || right < start)
        return 0; // 범위를 벗어나는 경우
 
    if (left <= start && end <= right)
        // segment tree 노드 구간[start, end]이
        // query 구간 [left, right]에 포함되는 경우
        return tree[node];
 
    int mid = (start + end) / 2;
    ll L = Query_Sum_SegmentTree(node * 2, start, mid, left, right);
    ll R = Query_Sum_SegmentTree(node * 2 + 1, mid + 1, end, left, right);
    return L + R;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    //freopen("Input.txt", "r", stdin);
 
    input();
 
    int treeHight = (int)ceil(log2(N));
    int treeSize = (1 << (treeHight + 1));
    tree.resize(treeSize);
    Make_SegmentTree(1, 0, N - 1);
 
    for (int i = 0; i < cmdList.size(); i++)
    {
        int cmd = cmdList[i].first;
        if (cmd == 1) {
            int idx = cmdList[i].second.first - 1;
            ll val = cmdList[i].second.second;
            ll diff = val - arr[idx];
            arr[idx] = val;
            Query_Update_SegmentTree(1, 0, N - 1, idx, diff);
        }
        else {
            int left = cmdList[i].second.first - 1;
            int right = cmdList[i].second.second - 1;
            cout << Query_Sum_SegmentTree(1, 0, N - 1, left, right) << endl;
        }
    }
}