구간 합 ( Prefix Sum )

구간합은 주어진 배열이나 리스트에서 원소들을 특정 구간으로 묶어
더한 값을 각 구간마다 계산하는 방법이다.

예를 들어, 주어진 배열이 [1, 2, 3, 4, 5] 라면 각 위치에서 구간합은 다음과 같다.

- 첫 번째 위치  : 1
- 두 번째 위치  : 1 + 2 = 3
- 세 번째 위치  : 1 + 2 + 3 = 6
- 네 번째 위치  : 1 + 2 + 3 + 4 = 10
- 다섯 번째 위치 : 1 + 2 + 3 + 4 + 5 = 15

배열에서 특정 구간의 합을 구할 때 매번 반복문을 돌며 합을 구하는 것은
시간 복잡도가 높아지기 때문에 구간합을 미리 구해 놓으면 구간 합을 구하는데
O(1)의 시간복잡도만 필요하다.

---

구간합을 구하는 공식은 다음과 같으며, 크게 2가지 과정을 거친다.

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

• 합배열 S를 만드는 공식,
  배열 S의 0번째 인덱스부터 S.length 까지 모든 배열을 이전값 + 현재 입력값으로 초기화

2. S[j] - S[i - 1]

• 구간합을 구하는 공식.
  구하려는 구간합의 인덱스가 더 큰 인덱스에서 더 작은 인덱스 - 1의 값을 빼면 구간합이 나온다.

예를 들어, 앞선 예제인 배열 [1, 2, 3, 4, 5] 에서 인덱스 3 ~ 4 구간합을 구하려면

1. 합배열을 만든다

int A[] = {1, 2, 3, 4, 5};
int S[] = new int[A.length + 1];

for (int i = 1 ; i < S.length ; i++) {
	S[i] = S[i-1] + A[i];
}

// S = {1, 3, 6, 10, 15}

2. 구간합을 구한다

int prefixSum = S[4] - S[3 - 1];
// S[4] = 15
// S[2] = 6 , prefix = 15 - 6, 정답 : 9

---

[백준] 구간합 구하기 4

-  Java Code


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 수의 개수
        int M = Integer.parseInt(st.nextToken()); // 합을 구해야하는 회수

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

        int S[] = new int[N + 1];
        S[1] = A[1];
        for (int i = 2 ; i < S.length ; i++) {
            S[i] = S[i-1] + A[i];
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            sb.append(S[end] - S[start - 1] + "\n");
        }

        System.out.println(sb);

    }