구간 합 구하기 - 2042

//2042 - 구간 합 구하기
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M, K;
long long arr[1000001];
 
struct SegmentTree
{
    int n;
    vector<long long> tree;
 
    SegmentTree(int n) : n(n), tree(4 * n + 1)
    {
        init(1, n, 1);
    }
 
    long long init(int left, int right, int node)
    {
        if (left == right)
            return tree[node] = arr[left];
        int mid = (left + right) / 2;
        return tree[node] = init(left, mid, node * 2) + init(mid + 1, right, node * 2 + 1);
    }
 
    long long query(int left, int right, int nodeLeft, int nodeRight, int node)
    {
        if (right < nodeLeft || nodeRight < left)
            return 0;
        if (left <= nodeLeft && nodeRight <= right)
            return tree[node];
 
        int mid = (nodeLeft + nodeRight) / 2;
        return query(left, right, nodeLeft, mid, node * 2) + query(left, right, mid + 1, nodeRight, node * 2 + 1);
    }
 
    long long query(int left, int right)
    {
        return query(left, right, 1, n, 1);
    }
 
    void update(int idx, long long val, int nodeLeft, int nodeRight, int node)
    {
        if (nodeLeft == nodeRight && nodeLeft == idx)
        {
            tree[node] += val;
            return;
        }
        if (nodeLeft <= idx && idx <= nodeRight)
        {
            tree[node] += val;
            int mid = (nodeLeft + nodeRight) / 2;
            update(idx, val, nodeLeft, mid, node * 2);
            update(idx, val, mid + 1, nodeRight, node * 2 + 1);
        }
    }
 
    void update(int idx, long long val)
    {
        update(idx, val, 1, n, 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i)
        cin >> arr[i];
    SegmentTree sg(N);
    long long flag, x, y;
    for(int i = 0; i<M+K; ++i)
    {
        cin >> flag >> x >> y;
        if(flag == 1)
            sg.update(x, y - arr[x]), arr[x] = y;
        else
            cout << sg.query(x, y) << "\n";
    }
}

 

 

 

 

 

 

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

2042번: 구간 합 구하기

 

 

 

 

 

 

구간 합 구하기

세그먼트 트리를 이용해 해결했습니다.