구간 합 (Prefix Sum)

구간 합이란?

• 배열이나 수열에서 일정 구간에 속한 원소들의 합을 빠르게 구하기 위해 사용하는 알고리즘이다.
• 시간 복잡도
  • 누적합 계산: O(n)
  • 구간합 쿼리: O(1)

 

왜 필요한가?

• 배열에서 구간 [i, j]의 합을 구할 때 매번 반복문을 돌리면 시간이 오래 걸린다.
• 한 번 전체 배열을 순회하며 누적합 배열을 만들어두면, 이후 각 구간의 합은 반복문 없이 한 번의 뺄셈으로 바로 계산할 수 있다.

---

구간 합 구하는 방법

public class PrefixSumExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // 0-based index
        int[] prefixSum = new int[arr.length];

        // 누적합 구하기
        prefixSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        // 예: 구간 [1, 3]의 합 구하기 => 2 + 3 + 4 = 9
        int i = 1, j = 3;
        int rangeSum = prefixSum[j] - (i > 0 ? prefixSum[i - 1] : 0);

        System.out.println("구간합: " + rangeSum);  // 출력: 9
    }
}

 

 

1. 누적 합 배열 구하기

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]   // A[0]부터 A[i]까지의 합

// 또는

S[i] = S[i -1] + A[i]

 

 

2. 구간 합 구하기

S[j] - S[i-1]    // i 에서 j 까지 구간 합

---

활용 예제

문제: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int numN = sc.nextInt();
        int psN = sc.nextInt();

        int[] s = new int[numN + 1];

        for(int i = 1; i <= numN; i++) {
            int num = sc.nextInt();
            s[i] += s[i - 1] + num;
        }

        for(int i = 0; i < psN; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(s[b] - s[a - 1]);
        }

        sc.close();
    }
}

---

사용 팁

• 대회나 코딩 테스트에서 "여러 번 구간의 합을 구하라"는 문제는 대부분 이 알고리즘이 쓰인다.
• 누적 값 배열을 만들 때, 크기를 n+1로 두고, prefixSum[0] = 0으로 시작하면 인덱스 예외를 피할 수 있다.