[백준 1275번] 커피숍2 (C++)

문제링크 : https://www.acmicpc.net/problem/1275

1275번: 커피숍2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[100001];
ll Tree[400001];  //세그먼트 트리

ll init(int start, int end, int node)  //트리 만들기
{
    if(start == end)  //노드가 리프 노드라면
    {
        return Tree[node] = arr[start];  //해당 원소 return
    }

    int mid = (start + end)/2;

    return Tree[node] = init(start, mid, node*2) + init(mid+1, end, node*2+1); //구간 합 구하기
}

ll sum(int start, int end, int left, int right, int node)  //start ~ end : 노드, left ~ right : 구간
{
    if(left > end || right < start) return 0;  //겹치지 않으므로 종료
    if (left <= start && end <= right) return Tree[node];  //교집합이 start, end
    int mid = (start + end) / 2;
    return sum(start, mid, left, right, node*2) + sum(mid+1, end, left, right, node*2+1);
}

void update(int start, int end, int node, int idx, ll diff)
{
    if(idx < start || idx > end) return;  //겹치지 않으므로 종료
    Tree[node] = Tree[node] + diff; //변한만큼 갱신

    if(start!=end)  //리프노드가 아니라면 자식도 갱신해줌
    {
        int mid = (start+end)/2;
        update(start, mid, node*2, idx, diff);    //왼쪽 탐색
        update(mid+1, end, node*2+1, idx, diff);  //오른쪽 탐색
    }
}

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

    int N, Q, x, y;
    ll a, b;  
    cin >> N >> Q;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    init(0, N-1, 1); //start, end, node

    for(int i=0; i<Q; i++)
    {
        cin >> x >> y >> a >> b;
        if(x > y)
        {
            cout << sum(0, N-1, y-1, x-1, 1) <<'\n';
        }
        else
        {
            cout << sum(0, N-1, x-1, y-1, 1) <<'\n';
        }
        update(0, N-1, 1, a-1, b-arr[a-1]); //start, end, node, idx, diff(변한 값)
        arr[a-1]=b;  //배열 갱신
    }

    return 0;
}

나의 첫 번째 골드 1 문제이며 세그먼트 트리의 웰노운 문제이다.

이 문제가 세그먼트 트리 문제인 것을 알고 풀어서, 미리 세그먼트 트리에 대한 내용 이론 및 구현 코드를 보면서 풀었기에 쉽게 풀었던 것 같다.

 

그래도 몇번 틀렸는데, tree 배열의 범위와 몇몇 변수들을 long long으로 선언하지 않아서 틀렸다.

이 문제의 입력되는 모든 수는 -2의 31제곱보다 크거나 같고, 2의 31제곱 - 1 보다 작거나 같은 정수라는 것을 보아 long long 범위인 것을 알 수 있다.

그렇기에 값을 다루는 변수 a, b를 long long으로 선언하고 마찬가지로 Tree 배열 또한 long long으로 선언해야 한다.

 

그리고 Tree의 범위를 4를 곱해준다면 메모리를 조금 낭비하기는 하지만 모든 경우에 대해서 배열의 크기가 넉넉하다는 것을 따로 검색하여 알았다.