[백준] 1275 - 커피숍 2(세그먼트 트리)

승래·2025년 11월 17일

1275 - 커피숍 2

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

1. 문제

문제
모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)

어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다.

그 게임은 다음과 같은 규칙을 갖는다.

N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게된다. 이 것을 번갈아 가면서 반복하는 게임이다.

당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.

당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만턴 정도 되는 게임을 기억할 수 있을 것이다. 몇판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.

입력
첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.

입력되는 모든 수는 -231보다 크거나 같고, 231-1보다 작거나 같은 정수이다.

출력
한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

2. 요구사항

전 문제인 [BOJ 2042] 구간 합 구하기를 통해 세그먼트 트리의 기본 구조와 long 타입의 중요성을 배웠다. 이번 문제는 그 쌍둥이 격인 커피숍2 문제다. 로직은 거의 동일하지만, 문제 조건에 숨어있는 '순서 뒤바짐' 함정을 처리하는 것이 핵심이었다.

문제 요구사항 분석

입력: 수의 개수 $N$ 과 턴의 개수 $Q$ (각각 최대 10만).
연산: 총 $Q$ 번의 턴이 진행되며, 각 턴은 두 단계로 이루어진다.

구간 합 구하기: $x$ 번째 수부터 $y$ 번째 수까지의 합을 구해서 출력한다.
수 변경하기: 그 후, $a$ 번째 수를 $b$ 로 바꾼다.

제약 사항:

입력되는 수는 int 범위( $-2^{31} \sim 2^{31}-1$ )이다.
하지만 구간 합은 int 범위를 넘을 수 있으므로 반드시 long을 사용해야 한다.
핵심 함정: 문제 조건에 $x > y$ 인 경우가 존재한다. (예: 5번째부터 2번째까지의 합을 구하라)

3. 접근 방식

(1) 자료구조 선택:
세그먼트 트리데이터 변경과 구간 합 구하기가 빈번하게 일어나므로, 일반 배열( $O(N)$ )로는 시간 초과가 발생한다. 따라서 $O(\log N)$ 으로 처리 가능한 세그먼트 트리를 사용했다.

(2) 데이터 타입 결정입력값 자체는 int 범위 내에 있지만, 10만 개의 데이터를 더하면 당연히 int 범위를 초과한다.이전 문제에서의 교훈을 되살려, tree 배열, diff, answer 등 값과 관련된 모든 변수는 처음부터 long으로 선언하여 오버플로우를 방지했다.

(3) 예외 처리 ( $x > y$ )문제 설명에 "x > y인 경우 y번째 부터 x번째이다" 라는 문구가 있다.세그먼트 트리의 sum 함수는 일반적으로 start <= end를 가정하고 작성된다. 따라서 쿼리를 수행하기 전에 $x$ 와 $y$ 의 대소를 비교하여, $x > y$ 라면 두 값을 Swap(교환) 해주는 로직을 추가했다.

// x가 y보다 크다면 순서를 바꿔서 작은 인덱스부터 시작하도록 조정
if (x > y) {
    answer = sum(segmentTree.tree, 1, 1, N, y, x);
} else {
    answer = sum(segmentTree.tree, 1, 1, N, x, y);
}

(4) Update 로직
값을 변경할 때는 diff (바꿀 값 - 기존 값)를 구해서, 해당 리프 노드와 부모 노드들에 더해주는 방식을 사용했다. 이때 원본 배열 arr도 갱신해줘야 다음 턴에서 올바른 diff를 구할 수 있다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class SegmentTree {
    long[] tree;

    public SegmentTree(int n) {
        tree = new long[n * 4];
    }

    public long init(long[] arr, int node, int start, int end) {
        if (start == end) {
            return tree[node] = arr[start];
        }

        return tree[node] = init(arr, node * 2, start, (start + end) / 2)
                + init(arr, node * 2 + 1, (start + end) / 2 + 1, end);
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        long[] arr = new long[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        SegmentTree segmentTree = new SegmentTree(N);
        segmentTree.init(arr, 1, 1, N);

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            long answer = 0;
            if (x > y) {
                answer = sum(segmentTree.tree, 1, 1, N, y, x);
            } else {
                answer = sum(segmentTree.tree, 1, 1, N, x, y);
            }
            System.out.println(answer);

            long diff = b - arr[a];
            arr[a] = b;
            update(segmentTree.tree, 1, 1, N, a, diff);
        }
    }

    static long sum(long[] tree, int node, int start, int end, int x, int y) {
        if (x > end || y < start) return 0;

        if (x <= start && y >= end) return tree[node];

        return sum(tree, node * 2, start, (start + end) / 2, x, y)
                + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, x, y);
    }

    static void update(long[] tree, int node, int start, int end, int a, long diff) {
        if (a < start || a > end) return;

        tree[node] += diff;

        if (start == end) return;

        update(tree, node * 2, start, (start + end) / 2, a, diff);
        update(tree, node * 2 + 1, (start + end) / 2 + 1, end, a, diff);
    }

}