[C++][백준 1275] 커피숍2

문제

접근 방법

상황만 부여했지 세그먼트 트리의 구간 합을 구하는 문제이다. 세그먼트 트리 문제를 풀어봤다면 쉽게 풀 것이라 생각하는데...

코드

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> nums, tree;
ll init(int start, int end, int node)
{
    if (start == end)
        return tree[node] = nums[start];
    int mid = (start + end) >> 1;
    return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}
ll find(int start, int end, int node, int left, int right)
{
    if (start > right || end < left)
        return 0;
    if (start >= left && end <= right)
        return tree[node];
    int mid = (start + end) >> 1;
    return find(start, mid, node * 2, left, right) + find(mid + 1, end, node * 2 + 1, left, right);
}
void update(int start, int end, int node, int target, ll diff)
{
    if (start > target || end < target)
        return;
    tree[node] += diff;
    if (start != end)
    {
        int mid = (start + end) >> 1;
        update(start, mid, node * 2, target, diff);
        update(mid + 1, end, node * 2 + 1, target, diff);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    nums.push_back(0);
    for (int i = 0; i < N; ++i)
    {
        int num;
        cin >> num;
        nums.push_back(num);
    }

    tree = vector<ll>((N << 2));
    init(1, N, 1);
    for (int i = 0; i < Q; ++i)
    {
        ll x, y, a, b;
        cin >> x >> y >> a >> b;
        if (x > y)
        {
            ll tmp = x;
            x = y;
            y = tmp;
        }
        cout << find(1, N, 1, x, y) << "\n";
        ll diff = b - nums[a];
        nums[a] = b;
        update(1, N, 1, a, diff);
    }
}

풀이

3가지를 유의해야 한다.
1. 기존 수의 배열의 값도 변경해줘야 한다. (diff를 구하는 과정에서 변경되지 않은 값이 사용될 수 있다)
2. diff를 구하는 과정에서 b가 int일 경우 오버플로우가 날 수 있다.
3. x와 y가 오름차 순이 아닐 수 있다.

실수하기 쉬운 부분들이다. 특히 3번의 경우에는 다른 유형의 문제에서도 지뢰처럼 숨겨져 있는 경우가 많다. 이번 문제는 노트에 친절히 적어뒀지만, 보통은 예제까지만 보기에 눈치채지 못한다. 나 또한 그랬다....