백준 2042 - 구간 합 구하기

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

 

입력으로 주어지는 수가 long long 범위에 있다는 사실에 유의하면서 세그먼트 트리 연산을 수행하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll ar[1000001];

int n, m, k;

inline int mid(int l, int r) { return l + (r - l) / 2; }

ll init(vector<ll> &tree, int node, int start, int end)
{
    if (start == end) return tree[node] = ar[start];
    int m = mid(start, end);
    return tree[node] = init(tree, node * 2, start, m) + init(tree, node * 2 + 1, m + 1, end);
}

void update(vector<ll> &tree, int node, int start, int end, int idx, ll diff)
{
    if (idx < start || idx > end) return;

    tree[node] += diff;

    if (start != end)
    {
        int m = mid(start, end);
        update(tree, node * 2, start, m, idx, diff);
        update(tree, node * 2 + 1, m + 1, end, idx, diff);
    }
}

ll sum(vector<ll> &tree, int node, int start, int end, int l, int r)
{
    if (start > r || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int m = mid(start, end);
    return sum(tree, node * 2, start, m, l, r) + sum(tree, node * 2 + 1, m + 1, end, l, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;

    for (int i = 1; i <= n; ++i)
        cin >> ar[i];
    
    vector<ll> segtree(n * 4);
    init(segtree, 1, 1, n);

    for (int i = 0; i < m + k; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c;

        if (a == 1)
        {
            ll diff = c - ar[b];
            ar[b] = c;
            update(segtree, 1, 1, n, b, diff);
        }
        else
        {
            cout << sum(segtree, 1, 1, n, b, c) << '\n';
        }
    }
}