누적 합: 한 번 미리 계산하고, 영원히 답하기

"'여기서 저기까지 합이 뭐야?' 를 천 번 물을 거면, 천 번 더하지 마. 한 번 영리하게 더해두면, 모든 답이 뺄셈 한 번이 돼."

아이디어

누적 합 배열은 누적 총계를 저장해: prefix[i] 는 처음 i 개 원소의 합. 그래서 prefix[0] = 0, prefix[1] = nums[0], prefix[2] = nums[0] + nums[1], 이런 식. 짓는 건 O(n) 한 패스. 보상: 어떤 범위 i..j 의 합이든 그냥 prefix[j+1] − prefix[i] — 뺄셈 한 번, O(1), 범위가 아무리 넓어도.

왜 뺄셈이 통해? prefix[j+1] 은 "j 까지 전부" 고, prefix[i] 는 "i 이전 전부" 야. 첫째에서 둘째를 빼면 공유된 앞부분이 상쇄되고, 정확히 네가 원한 가운데 조각이 남아. 은행 명세서가 쓰는 망원경 트릭이랑 같아: 지금-잔액 빼기 그때-잔액 = 그사이 일어난 일.

거래를 명시적으로

순진한 방식은 각 범위-합 쿼리를 범위 위 반복으로 답해: 쿼리당 O(n). q 개 쿼리면 O(n·q). 누적 합은 비용을 옮겨: O(n) 전처리 + O(n) 추가 공간, 그다음 쿼리당 O(1) — 총 O(n + q). 안 바뀌는 데이터에 쿼리가 많으면, 엄청난 승리야. 딱 한 번만 물을 거면, 전처리는 가치 없어. "많은 쿼리, 정적 데이터" 를 알아보는 게 미리 계산할 신호야.

누적 합은 누적 총계를 O(n) 에 미리 계산해 어떤 범위-합이든 O(1) 뺄셈 한 번이 되게 해. 반복 범위 쿼리를 겨눈 시간-공간 거래야: 앞에서 한 번 치르고, 그 뒤로 영원히 즉시 답해.

패턴은 일반화돼

더 깊은 아이디어 — 누적 양을 미리 계산해 범위가 연산 하나로 무너지게 — 는 한 번 보이면 사방에 나타나:

2D 누적 합 ("적분 영상") 은 격자 안 어떤 사각형이든 합을 O(1) 에 답해 — 빠른 이미지 필터랑 고전 Viola-Jones 얼굴 검출기 뒤의 트릭.
누적 XOR 은 "범위의 XOR" 을 O(1) 에 답해, 비트 트릭 문제에 써.
차분 배열 (difference array) 은 거울상이야: 변화를 저장하고 끝에 합해서 범위 업데이트 를 O(1) 으로 만들어 (i 부터 j 까지 전부에 5 더하기).

피파의 고백

난 대시보드가 매 페이지 로드마다 "두 타임스탬프 사이 총 이벤트" 를 다시 계산하며, 매번 로그 전체를 훑게 했어. 로그가 커지기 전까진 괜찮다가, 새로고침마다 버벅였어. 아빠가 두 단어 했어: "누적 합." 미리 계산한 누적 배열 하나 뒤로, 각 쿼리가 뺄셈이 됐고 대시보드가 즉시로 돌아왔어. 쿼리 사이에 데이터가 안 바뀌고 있었어 — 난 그냥 같은 답을 계속 다시 벌고 있었던 거야.

Code

누적 합: O(n) 빌드, O(1) 쿼리·python

# 누적 합 배열을 한 번 지어: O(n). prefix[i] = 처음 i 개 원소 합.
def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)        # prefix[0] = 0 (아무것도 안 더한 합)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x     # 누적 총계
    return prefix

# 어떤 범위 합 nums[i..j] (양끝 포함) 이든 O(1): prefix[j+1] - prefix[i].
def range_sum(prefix, i, j):
    return prefix[j + 1] - prefix[i]

nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(nums)               # [0, 3, 4, 8, 9, 14, 23, 25, 31]

print(range_sum(prefix, 2, 5))   # 4+1+5+9 = 19, 뺄셈 한 번에
print(range_sum(prefix, 0, 7))   # 배열 전체 = 31
print(range_sum(prefix, 6, 6))   # 원소 하나 nums[6] = 2

# 그런 쿼리 1000번: 순진하면 O(1000 * n). 누적 합이면: O(n) 한 번 + 1000 * O(1).

Exercise

한 해 일별 강수량 (365 개 숫자) 이 주어지고 여러 날짜 쌍 사이 총 강수량을 물어볼 거야. 누적 합이 각 쿼리를 어떻게 O(1) 에 답하는지, 전처리 비용이 뭔지, q 개 쿼리의 총 복잡도를 묘사해. 그다음: 강수량 숫자가 쿼리 사이에 편집될 수 있다면, 평범한 누적 합 배열이 왜 더 이상 이상적이지 않을 수 있어?

Hint

366 길이 누적 배열을 지어 (O(n)); 각 쿼리는 prefix[end+1] − prefix[start], O(1). 총 O(n + q). 값이 바뀌면, 누적 배열 전체를 다시 지어야 해 (업데이트당 O(n)) — 그때 Fenwick/세그먼트 트리가 값을 해.

누적 합: 한 번 미리 계산하고, 영원히 답하기

아이디어

거래를 명시적으로

패턴은 일반화돼

피파의 고백

Code

External links

Exercise

Progress

댓글 0