누적합(Prefix Sum)

1. 누적합(Prefix Sum)이란?

- 배열이나 리스트의 각 원소까지의 합을 미리 계산해두고, 이를 이용하여 임의의 구간 합은 빠르게 구하는 기법이다.

- 입력 배열의 앞에서 부터 누적된 합을 저장한 누적합 배열을 만들어서 사용한다.

- 여러 구간 합, 평균, 최대/최소 문제 등을 빠른 시간으로 구할 때 사용된다.

 

2. 누적합 점화식

- 누적합 배열 P와 일반 배열 A일때

   - P[0] = A[0]

   - P[i] = P[i-1] + A[i] for i >= 1

- 구간 [l, r]의 합은 다음과 같다.

   - 만약 l = 0이면, 구간 합은 P[r]

   - 만약 l > 0이면, 구간 합은 P[r] - P[l-1]

 

3. 누적합 구현

- 누적합 배열을 생성하고 두 개의 구간합 쿼리를 해결하는 문제이다.

public class PrefixSum {
    public static void main(String[] args) {
        // 예제 데이터
        int[] arr = {2, 4, 5, 7, 1, 3};
        int n = arr.length;

        // 누적합 배열 생성
        int[] prefixSum = new int[n];
        prefixSum[0] = arr[0];
        for(int i = 1; i < arr.length; i++) {
            prefixSum[i] = prefixSum[i-1] + arr[i];
        }

        int q_l = 1;
        int q_r = 3;

        int sum = 0;
        if(l == 0) {
            sum = prefixSum[r];
        } else {
            sum = prefixSum[r] - prefixSum[l - 1];
        }

        // 출력: 16
        System.out.println(sum);
    }
}