누적 합 (prefix sum)

누적 합 (prefix sum)

• 수열(sequence, 수 또는 다른 대상의 순서 있는 나열) An에 대해 특정 구간의 합을 말함

• int[] a = new Int[100000]; 10만 개의 요소가 적재된 a 배열를 이용하여 특정 구간의 합을 구할 때 단순히 for문으로 sum += a[i] 을 사용할 경우 시간복잡도가 높아짐

• 누적합 배열(prefix array)을 생성하고 해당 배열의 구간시작인덱스와 구간끝인덱스를 사용하여 구간의 합을 구하면 됨

• 식 : f(a, b) = f(b) - f(a-1), (a<=b)
  f(b) : 1부터 b까지의 합 (누적합 배열의 b인덱스에 b까지의 누적 합이 들어있음)
  f(a-1) : 1부터 a-1까지의 합 (누적합 배열의 a-1인덱스에 a-1까지의 누적합이 들어있음)

  자세한 설명은 아래 링크 참조
  누적 합 설명 블로그 by nahwasa

연습 문제

• 백준 11659번 - JAVA 풀이
  구간 합 구하기 4

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

public class PrefixSumEx1 {

	public static void main(String[] args) throws IOException {
		// BufferedReader, StringTokenizer 대용량 입출력 시 사용함 (성능에 좋음)
		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());

		// 누적합 배열을 생성한다
		// index를 1부터 시작한 이유: 시작Index, 끝Index 처리가 쉬워진다
		// 구간 입력 예시가 [1, 3], [5, 5] 이런식으로 되어 있음
		int[] prefixSum = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			prefixSum[i] = prefixSum[i - 1] + Integer.parseInt(st.nextToken());
		}

		// 누적합 배열의 끝index 값에서 시작index-1 값을 빼면
		// 구간의 시작부터 끝까지의 합이 나옴
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			System.out.println(prefixSum[e] - prefixSum[s - 1]);
		}
	}
}