[코테준비] Prefix Sum 패턴

0. 기본 개념부터 10초 정리

배열 A가 있을 때,

 

A: [a0, a1, a2, a3, ..., aN-1] prefix[i] = A[0] + A[1] + ... + A[i-1] // 길이 N+1짜리, prefix[0] = 0

이렇게 만들면,

 

[L, R] 구간합 = prefix[R+1] - prefix[L]

→ 그래서 **“구간 합 여러 번 물어보는 문제”**에서

• 누적합 만들 때: O(N)
• 각 쿼리 답변: O(1)
• 전체: O(N + Q)

이게 2번 문제에서 자주 나오는 패턴이야.

 

정수 배열 A가 있어.

예를 들어:

 

A = [2, 4, 6, 8, 10]

그런데 문제에서 “구간의 합”을 여러 번 물어봐.

예를 들어 쿼리(질문)가 세 개라고 하면:

 

쿼리 1: L=0, R=2 → A[0] + A[1] + A[2] = 2 + 4 + 6 = 12 쿼리 2: L=1, R=3 → 4 + 6 + 8 = 18 쿼리 3: L=2, R=4 → 6 + 8 + 10 = 24

이렇게 범위(L, R)마다 합을 계산해서 리턴해야 하는 문제가 아주 흔함.

---

❗ 문제: 합을 매번 직접 계산하면 너무 느림

예:

 

A의 길이가 100,000 쿼리 수가 100,000

만약 쿼리마다 for문으로 합을 구하면:

 

O(N) * O(Q) = 100,000 * 100,000 → 10억 → 시간 초과

그래서 나온 개념이 Prefix Sum(누적합)

---

⭐ Prefix Sum 아이디어

A 배열의 앞에서부터 누적해서 더한 배열을 만들어.

 

A = [2, 4, 6, 8, 10] prefix = [0, 2, 6, 12, 20, 30] ↑ prefix[0] = 0 prefix[i] = A[0] ~ A[i-1] 합

그리고 구간 합(L,R)은 이렇게 1초만에 끝나:

 

sum(L,R) = prefix[R+1] - prefix[L]

 

---

✔ 왜 되는지 예로 볼게

예: 구간 [1, 3] = A[1]+A[2]+A[3]

• prefix[4] = A[0]+A[1]+A[2]+A[3] = 20
• prefix[1] = A[0] = 2

 

prefix[4] - prefix[1] = 20 - 2 = 18

정답: 4 + 6 + 8 = 18

---

👍 즉, 이 문제의 의미는

“배열이 있고, 여러 개의 [L,R] 범위를 빠르게 더해야 한다”

이걸 표현한 게:

• A: 원본 배열
• L[i]: i번 쿼리의 왼쪽 인덱스
• R[i]: i번 쿼리의 오른쪽 인덱스
• 구간합 = prefix[R[i] + 1] - prefix[L[i]]

---

1. 예제 1 – 가장 기본 “구간 합 빠르게 구하기”

문제 느낌

정수 배열 A와 쿼리들 L[i], R[i]가 주어질 때,
각 쿼리마다 A[L[i]..R[i]] 합을 반환하라.

Prefix Sum 패턴 정리 (시험용 암기 포인트)

기본 템플릿 

int N = A.length;

long[] prefix = new long[N + 1];

prefix[0] = 0;

for (int i = 0; i < N; i++) {

prefix[i + 1] = prefix[i] + A[i];

}

구간 합

long rangeSum = prefix[R + 1] - prefix[L]

 

1. 0/1 카운트, 특정조건 개수 세기
   • prefix[i+1] = prefix[i] + (조건 ? 1 : 0);
   • 구간 내 개수 = prefix[R+1] - prefix[L]
2. 쌍 세기 / 후행 원소 개수 필요할 때
   • 전체 개수 = prefix[N]
   • 뒤에 남은 개수 = prefix[N] - prefix[i+1] 같은 형태