[Algorithm] 구간 합 (Prefix Sum)

구간 합 (Prefix Sum)

■ 정의

- 수들의 나열에서 특정 구간의 합을 의미
- 보통 1차원 배열에서 인덱스 사이의 값들의 합을 구하는데 사용

 

■ 구간 합 알고리즘

- 구간 합 공식: sum[j] - sum[i - 1]  // i에서 j까지의 구간 합
- 합 배열(P)을 미리 계산해 두면 구간 합은 한 번에 계산 가능
- 알고리즘의 시간복잡도: O(1)

 

■ Code 

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

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

        int[] arr = new int[N + 1];

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

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

            System.out.println(arr[b] - arr[a - 1]);
        }
    }
}

 

---

■ 백준 No.11659

11659번: 구간 합 구하기 4