누적합·차분 배열

누적합 (prefix sum)

배열 a[0..n)의 구간 합 a[l]+…+a[r-1]을 여러 번 물을 때.

pref[0] = 0
pref[i+1] = pref[i] + a[i]
sum(l, r) = pref[r] - pref[l]

전처리 O(n), 질의 O(1).

const pref = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
function sum(l, r) { return pref[r] - pref[l]; }

2차원 맛보기

격자 구간 합도 비슷한 아이디어입니다.
모서리 포함 관계를 그림으로 확인하세요 (오프바이원 천국).

차분 배열

같은 값으로 구간 [l, r)에 더하기를 여러 번 할 때:

diff[l] += v
diff[r] -= v

마지막에 누적하면 결과 배열이 됩니다. 갱신 O(1), 최종 O(n).

언제 쓰나

• 구간 합 질의가 많다
• 슬라이딩 윈도우 합의 형제로 생각할 수 있다
• “매 쿼리마다 루프”가 제약을 못 견딜 때

함정

• pref 길이 n+1과 인덱스 약속
• 오버플로 (합이 커지면 big int / long long)
• 빈 구간 l === r → 합 0

구간 합 질의 예

배열 2 3 5 7, 구간 [1, 4) 합 = 3+5+7=15.

pref: 0 2 5 10 17
pref[4]-pref[1]=15

차분으로 구간 가산 예

초기 0열, [1,3)에 +5 두 번:

diff: 0 +5 0 -5 0
누적: 0 5 5 0 0

관련

슬라이딩 윈도우 합은 “이동하는 구간 합”이고, 누적합은 “임의 구간 합”입니다.
둘 다 구간을 O(1)에 가깝게 다루려는 도구입니다.

더 깊게

읽은 뒤 연습장에서 예제 코드를 한 번 타이핑해 보세요. 눈으로만 보면 하루 뒤 사라집니다.

관련 원리 카드와 문제 태그로 바로 이어서 풀면, 문법·패턴이 한 묶음으로 남습니다.

막히면 30분 규칙: 입력을 로그로 확인 → 기대/실제 한 줄 비교 → 그래도 안 되면 배우기 레슨으로 잠시 복귀.