[백준][Java] 19951 - 태상이의 훈련소 생활

1. 문제 정보

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

19951번: 태상이의 훈련소 생활

난이도 : G5

유형 : 누적합, 펜윅 트리, 세그먼트 트리

시간 : O((N + M)logN)

---

2. 풀이

업데이트 쿼리가 [2, 4] 일 시 "prefixSum[2] += 변화량, prefixSum[4 + 1] -= 변화량"

이 방식으로 처리하는 범위 누적합 기법을 사용하지 않고 펜윅 트리로 풀어 보았다.

 

웰노운 방식보다 느리지만 펜윅 트리로 범위 누적합 쿼리 문제를 푸는 연습에 도움이 되었다.

---

3. 코드

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

public class Main {

    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    int N;
    int M;
    int[] prefixSum;

    private void rangeUpdate(int start, int end, int value) {
        update(start, value);
        update(end + 1, -value);
    }

    private void update(int idx, int value) {

        while (idx <= N) {
            prefixSum[idx] += value;
            idx += idx & -idx;
        }
    }

    private int query(int idx) {

        int sum = 0;
        while (idx > 0) {
            sum += prefixSum[idx];
            idx -= idx & -idx;
        }
        return sum;
    }

    private void solution() throws IOException {

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        prefixSum = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int value = Integer.parseInt(st.nextToken());
            rangeUpdate(i, i, value);
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            rangeUpdate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        for (int i = 1; i <= N; i++) {
            sb.append(query(i)).append(" ");
        }

        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        main.solution();
    }
}