백준 2268 - 수들의 합

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

 

최대 10만건의 구간 수정과 합을 구할 것을 요구하는 문제이다. 세그먼트 트리를 통해 원하는 질의를 빠르게 수행하면 된다.

 

배열의 초기 조건은 주어지지 않았으므로 세그먼트 트리를 초기화 할 필요 없이 sum과 update 연산만 구현하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int ar[1000000];

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

ll sum(vector<ll> &tree, int node, int stt, int end, int l, int r)
{
    if (l <= stt && end <= r) return tree[node];
    if (l > end || r < stt) return 0;

    int m = mid(stt, end);

    return sum(tree, node * 2, stt, m, l, r) + sum(tree, node * 2 + 1, m + 1, end, l, r);
}

void update(vector<ll> &tree, int node, int stt, int end, int idx, ll diff)
{
    if (idx < stt || idx > end) return;
    tree[node] += diff;

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

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

    int n, m;
    cin >> n >> m;

    vector<ll> seg(n * 4);

    while (m--)
    {
        int qry, a, b;
        cin >> qry >> a >> b;

        if (!qry)
        {
            int l = min(a - 1, b - 1), r = max(a - 1, b - 1);
            cout << sum(seg, 1, 0, n - 1, l, r) << '\n';
        }
        else
        {
            ll dif = b - ar[a - 1];
            ar[a - 1] = b;
            update(seg, 1, 0, n - 1, a - 1, dif);
        }
    }
}