[Java] 구간 합(Prefix Sum)

구간 합(Prefix sum)은 무엇이며 어떠한 경우에 활용될까?

 

문제 예시

• 아래와 같이 N개의 정수로 구성된 수열이 있습니다.
• M개의 쿼리(Query) 정보가 주어집니다.
  • 각 쿼리는 L과 R로 구성됩니다.
  • [L, R] 구간에 해당하는 데이터들의 합을 모두 구해보세요.

1) L = 1, R = 3

2) L = 2, R = 5

         ...

M) L = 3, R = 4

 

 

나의 풀이

구간 합을 이용하지 않고 구현한 내풀이는 아래와 같다.

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int m = Integer.parseInt(br.readLine());

    int[] arr = {10, 20, 30, 40, 50};

    for (int i = 0; i < m; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int l = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        int sum = 0;
        for(int j = l-1; j<=r-1; j++){
            sum += arr[j];
        }
        bw.write(sum + "\n");
    }

    bw.flush();
    bw.close();

}

배열은 arr을 선언해주었고, 쿼리의 개수 M과 구간[L, R]은 M번 입력받는 형태이다. 그냥 배열에서 인덱스 L부터 R까지 더하면되는 누구나 쉽게 떠올릴 수 있는 방법이다.

 

실행 결과:

구간합은 무엇이며 위의 풀이 방법과 어떠한 차이가 있을까?

 

 

구간 합(Prefix Sum)

구간 합의 원리는 다음과 같다.

예를 들어 구간 L = 3, R = 5일 때 합이 120인 과정을 구간합으로 구해보면 아래 그림과 같다.

구간[3, 5]는 구간[1, 5]까지의 구간합과 구간[1, 2]까지의 구간합의 차와 같다.

이러한 특성을 이용하는 것이 구간 합이다.

 

 

구간 합을 활용한 알고리즘 설명

1. Prefix Sum을 계산하여 배열 P에 저장한다. (P는 구간의 누적 합)
2. 매 M개의 쿼리 정보를 확인할 때, 구간 합은 P[R] - P[L - 1]이다.

1) L = 1, R = 3  => P[3] - P[0] = 60

2) L = 2, R = 5  => p[5] - p[1] = 140

...

M) L =3, R = 4  => p[4] - p[2] = 70

 

int n = 5;
int[] arr = {10, 20, 30, 40, 50};

int[] p = new int[arr.length + 1];

p[0] = 0;
for (int i = 1; i < p.length; i++) {
    p[i] = p[i - 1] + arr[i-1];
}

int l = 3;
int r = 5;
System.out.println("Prefix Sum = " + (p[5] - p[2]));

실행 결과:

Prefix Sum = 120