합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

구간 합의 핵심 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 배열 A가 있을 때 합 배열 S는 다음과 같이 작성한다.

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

합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다.

합 배열을 미리 구하면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소하게 된다.

합 배열 S를 만드는 공식

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

이렇게 구한 합 배열을 이용해 i에서 j까지의 구간 합을 구할 수 있다.

구간 합을 구하는 공식

S[j] - S[i-1]

문제 : 구간 합 구하기 [백준 11659]

import java.util.Scanner;

public class 구간합_11659 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt(); //1 <= N <= 100,000 //숫자 개수
        int M = scan.nextInt(); //1 <= N <= 100,000 //질의 개수

        int[] arr = new int[N+1]; // 1부터 시작임.
        for(int i=1; i < N+1; i++) {
            int temp = scan.nextInt();
            arr[i] = arr[i-1] + temp;
        }

        for(int k=0; k < M; k ++) {
            int i = scan.nextInt();
            int j = scan.nextInt();
            System.out.println(arr[j] - arr[i-1]);
        }
    }
}