[C++][백준 2042] 구간 합 구하기

문제

접근 방법

변형이 이루어지는 구간 합을 구하는 문제이다.
세그먼트 트리를 구현하라고 의도한 문제이다.

세그먼트 트리란 구간 합을 트리 형태로 만들어서 저장해두는 것으로 재귀 형태로 구현하면 쉽게 할 수 있는 것 같다.

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
vector<ll> segTree;
vector<ll> numV;
int N, M, K;
ll init(int start, int end, int node)
{
    if (start == end)
        return segTree[node] = numV[start];
    int mid = (start + end) >> 1;
    return segTree[node] = init(start, mid, node << 1) + init(mid + 1, end, (node << 1) + 1);
}
ll sum(int start, int end, int left, int right, int node)
{
    if (left > end || right < start)
        return 0;
    if (left <= start && right >= end)
        return segTree[node];
    int mid = (start + end) >> 1;
    return sum(start, mid, left, right, node << 1) + sum(mid + 1, end, left, right, (node << 1) + 1);
}
void update(int start, int end, int target, ll diff, int node)
{
    if (target > end || target < start)
        return;
    segTree[node] += diff;
    if (start == end)
        return;
    int mid = (start + end) >> 1;
    update(start, mid, target, diff, node << 1);
    update(mid + 1, end, target, diff, (node << 1) + 1);
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> K;
    int h = ceil(log2(N));
    int treeSize = 1 << (h + 1);
    segTree = vector<ll>(treeSize);
    numV.push_back(0);
    for (int i = 0; i < N; ++i)
    {
        ll num;
        cin >> num;
        numV.push_back(num);
    }
    init(1, N, 1);
    for (int i = 0; i < M + K; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            ll diff = c - numV[b];
            numV[b] = c;
            update(1, N, b, diff, 1);
        }
        else
        {
            cout << sum(1, N, b, c, 1) << "\n";
        }
    }
    return 0;
}

풀이

입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

2퍼센트에서 틀린다면 자료형을 확인해봐야 한다.
init, sum의 경우 반환형을 long long으로 해주어야 한다. update에 보정해주는 값 또한 long long으로 해주어야 하며 숫자들의 입력도 long long으로 해주어야 한다.
init의 반환형을 long long으로 해줬어야 했는데 안 해줘서 헤맸다. (처음에 자료형을 생각 안 하고 적어줘서 int로 해두었다)

처음 세그먼트 트리에 대해 알게 됐을 때는 대충 보고 어렵다고 생각했는데 재귀를 활용하니 쉽게 만들어지고 좋은 자료구조인 것 같다.