Lv.1 초급

누적합

구간 합 질의를 뺄셈 한 번(O(1))으로. 질의가 많은 문제의 표준 전처리이며 2차원 격자로 확장됩니다.

지문 신호“구간의 합”“여러 번 질의”“직사각형 영역”

0/4 해결

눈으로 보기

재생을 누르고 단계별로 동작을 따라가세요

arr

1/11누적합: 구간 합 질의가 많을 때, 매번 더하는 대신 "처음부터 i까지의 합" 배열 P를 한 번만 만들어 둡니다. P[0] = 0에서 시작합니다.

위 = 원본 배열, 아래 = 누적합 P구간 [l, r] 합 = P[r+1] − P[l]

개념 이해

핵심 패턴 코드는 손으로 따라 쳐 보는 것을 권장

1 / 8

비유로 이해하기

고속도로 표지판에는 "서울에서 132km"처럼 출발지부터의 누적 거리가 적혀 있습니다. 그래서 132km 지점과 87km 지점 사이의 거리를 알고 싶을 때, 그 구간을 다시 달려보며 재지 않고 132 - 87 = 45로 즉시 답합니다. 표지판을 한 번 세워두는 수고를 들여, 이후의 모든 질문을 뺄셈 한 번으로 바꾼 것입니다.

누적합은 "처음부터 여기까지의 합"을 미리 만들어 두고, 구간 합을 뺄셈 한 번(O(1))으로 답하는 전처리 기법입니다.

준비: 각 지점마다 출발지부터의 누적 거리를 적어둔다 (한 번, O(N))
질의: 어떤 구간이든 끝 표지판 - 시작 표지판 (매번, O(1))

[3, 1, 4, 1]에 대해 표지판 배열 P를 만들어 봅니다. P는 원본보다 한 칸 길고, 맨 앞은 "아직 아무것도 안 갔다"는 뜻의 0입니다.

위치	0	1	2	3	4
원본 `arr`	—	3	1	4	1
누적 `P`	0	3	4	8	9

이제 질문에 답해 봅니다. 1번부터 2번까지(값 1과 4)의 합은 얼마일까요.

질의	계산	결과	검산
`[1, 2]` 구간 합	`P[3] - P[1]` = 8 - 3	5	1 + 4 = 5
`[0, 3]` 전체 합	`P[4] - P[0]` = 9 - 0	9	3+1+4+1 = 9

맨 앞에 0을 둔 덕분에 l = 0인 구간도 예외 없이 같은 공식으로 처리됩니다. 경계 실수의 대부분이 이 패딩을 안 둬서 생깁니다.

0으로 시작하는 P를 만듭니다 — 빈 구간을 뜻하는 한 칸 패딩입니다.

const P = [0]; // P는 원본보다 1 길다 — P[0] = 0 (빈 구간)

앞에서부터 하나씩 더해 채웁니다 — 직전 누적값에 현재 값을 더하면 끝입니다.

for (const v of arr) P.push(P[P.length - 1] + v);

질의는 뺄셈 한 번입니다 — 0-기반, 양끝 포함 기준입니다.

const rangeSum = (l: number, r: number) => P[r + 1] - P[l];

전체 코드 — "구간 질의 목록에 답하기":

function solution(arr: number[], queries: [number, number][]): number[] {
  // 1단계: 패딩 한 칸으로 시작
  const P = [0];
  // 2단계: 앞에서부터 누적
  for (const v of arr) P.push(P[P.length - 1] + v);
  // 3단계: 각 질의를 뺄셈 한 번으로 — 질의가 몇 개든 O(1)씩
  return queries.map(([l, r]) => P[r + 1] - P[l]);
}

2차원 누적합 — 격자에서 직사각형 구간 질의가 많으면 2D로 확장합니다.

// P[i][j] = (0,0)~(i-1,j-1) 직사각형의 합 (한 칸 패딩)
const P = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
for (let i = 1; i <= n; i++)
  for (let j = 1; j <= m; j++)
    P[i][j] = grid[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1];
 
// (r1,c1)~(r2,c2) 합 — 포함·배제 원리
const sum2d = (r1: number, c1: number, r2: number, c2: number) =>
  P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];

더하고-빼는 부호가 헷갈리면 그림을 그리세요: 큰 사각형에서 위·왼쪽 띠를 빼면 왼쪽 위 모서리가 두 번 빠지므로 다시 더합니다.

누적합 + 해시 — 한 단계 위

"합이 정확히 K인 연속 부분 배열의 개수"는 슬라이딩 윈도우가 아니라(음수 가능 시) 이 조합입니다.

// P[j] - P[i] = K  ⇔  P[i] = P[j] - K  → "그런 P[i]를 몇 번 봤는가"
function countSubarrays(arr: number[], K: number): number {
  const seen = new Map<number, number>([[0, 1]]);
  let prefix = 0, count = 0;
  for (const v of arr) {
    prefix += v;
    count += seen.get(prefix - K) ?? 0;
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }
  return count;
}

P를 원본과 같은 길이로 만들어 l = 0 구간을 따로 처리 — 패딩 한 칸이 답

const bad = [arr[0]]; // 잘못된 코드 — l이 0일 때만 분기가 하나 더 필요해집니다
const good = [0];     // 고친 코드 — 모든 구간이 같은 공식

공식 혼동: [l, r] 합은 P[r+1] - P[l] (r - l이 아님)

const bad = P[r] - P[l];      // 잘못된 코드 — 오른쪽 끝 원소가 빠집니다
const good = P[r + 1] - P[l]; // 고친 코드

2D에서 - P[r1][c1]을 +로 — 포함·배제 부호 실수

// 잘못된 코드: P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] - P[r1][c1]
// 고친 코드:   P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

갱신이 잦은 문제에 누적합 고집 — 값이 자주 바뀌면 매번 재계산 O(N). (그 경우는 다른 도구의 영역)

왜 O(1)인가: P[i]는 "0번부터 i-1번까지의 합"이라는 하나의 약속이고, 구간 합은 두 약속의 차입니다. 겹치는 앞부분이 정확히 상쇄되므로 구간 길이와 무관하게 뺄셈 한 번입니다.
차이 배열(구간 갱신용): 질의가 아니라 "구간 [l, r]에 v를 더하기"가 여러 번 들어오는 문제는 반대로 씁니다. D[l] += v; D[r+1] -= v;를 모두 처리한 뒤, 마지막에 D의 누적합을 취하면 최종 배열이 나옵니다. 갱신 M번이 O(M + N)으로 끝납니다.

function applyRanges(n: number, ops: [number, number, number][]): number[] {
  const D = new Array(n + 1).fill(0);
  for (const [l, r, v] of ops) { D[l] += v; D[r + 1] -= v; }
  const res: number[] = [];
  let acc = 0;
  for (let i = 0; i < n; i++) { acc += D[i]; res.push(acc); }
  return res;
}

갱신과 질의가 둘 다 잦으면: 누적합은 갱신마다 O(N) 재계산이라 버팁니다. 이때는 세그먼트 트리·펜윅 트리처럼 갱신과 질의를 모두 O(log N)으로 처리하는 자료구조가 답입니다.
값이 커질 때: 원소가 크고 N이 수십만이면 누적합이 2^53을 넘길 수 있습니다. 모듈로가 지정된 문제라면 누적 단계마다 % MOD를 적용하되, 뺄셈 결과가 음수가 될 수 있으므로 ((x % MOD) + MOD) % MOD로 감쌉니다.

문제로 확인

난이도 순서대로 4문제 — 막히면 개념으로 돌아왔다 다시

1구간 합 쿼리#067다음 풀 문제쉬움 2동료 배율 합산 점수#019중간 3기상 격자 구역 조회#101중간 4축제 셔틀버스 혼잡 구간#119어려움