누적 합: 한 번 쌓아두고 계속 답하기

"'여기서 저기까지 합이 얼마야?'를 천 번 물을 거면 천 번 더하고 있지 마. 처음에 한 번만 영리하게 쌓아두면 그다음부터는 모든 답이 뺄셈 한 번이야."

아이디어

누적 합 배열에는 앞에서부터의 합계를 차곡차곡 담아. 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