알고리즘Prefix SumSegment TreeRange QueryArray

누적합과 세그먼트 트리

같은 배열에서 구간 합을 구하고 값 하나를 바꿨을 때 다시 계산하는 범위를 비교합니다

시각화 로드 중...

개요

Algorithm Overview

여러 번 구간 합을 구해야 할 때는 합을 미리 저장해 둘 수 있습니다. 누적합은 배열 앞부분의 합을 한 줄에 저장하고, 세그먼트 트리는 배열을 나눈 여러 구간의 합을 트리에 저장합니다. 이 차이는 원본 배열의 값이 바뀔 때 드러납니다.

01

누적합으로 조회하기

배열의 인덱스는 0부터 시작합니다. 누적합 P[i]에는 앞에서부터 원소 i개의 합을 저장합니다. P[0] = 0에서 시작해 P[i + 1] = P[i] + A[i]로 다음 칸을 채웁니다.

양끝을 포함하는 [L, R]의 합은 P[R + 1] − P[L]입니다. 예제 배열 [4, 2, -1, 5, 3, 6, -2, 7]에서 [1, 6]의 합은 P[7] − P[1] = 17 − 4 = 13입니다.

02

세그먼트 트리로 조회하기

리프는 배열 원소 하나를 저장합니다. 부모는 서로 겹치지 않는 두 자식 구간의 합을 저장합니다. 루트에서 시작해 노드의 구간을 조회 범위와 비교합니다.

  • 조회 범위에 완전히 들어가는 노드는 저장된 합을 더하고 그 아래는 탐색하지 않습니다.
  • 조회 범위와 겹치지 않는 노드는 건너뜁니다.
  • 일부만 겹치면 두 자식 구간을 확인합니다.

예제에서는 [1, 1], [2, 3], [4, 5], [6, 6]의 합을 더합니다. 네 구간이 겹치지 않으면서 [1, 6]을 빠짐없이 덮으므로 2 + 4 + 9 + (-2) = 13입니다. 트리에서 리프의 구간은 [i]로 줄여 표시합니다.

03

값 하나를 바꾸면

A[2]를 -1에서 4로 바꾸면 차이는 +5입니다. 누적합에서는 인덱스 2를 포함하는 P[3]부터 P[8]까지 6칸에 차이를 더합니다. 트리에서는 리프 [2, 2]와 그 조상 [2, 3], [0, 3], [0, 7]까지 4개 노드만 다시 계산합니다. 두 방식 모두 갱신 후 [1, 6]의 합은 18입니다.

연산별 복잡도

연산누적합세그먼트 트리
초기 구성O(n)O(n)
구간 합 조회O(1)O(log n) 최악
원소 한 개 갱신O(n) 최악O(log n)
추가 공간O(n)O(n)

월별 매출처럼 원본을 고정해 두고 조회가 많은 데이터에는 누적합이 간단합니다. 개별 기록이 자주 바뀌고 구간 합도 계속 조회한다면 세그먼트 트리가 갱신 범위를 줄여 줍니다.

학습 목표

  • 양끝을 포함한 [L, R]의 합을 두 누적합으로 계산할 수 있다.
  • 트리 노드를 완전히 포함, 일부 겹침, 범위 밖으로 구분할 수 있다.
  • 한 원소를 바꿨을 때 갱신하는 누적합 칸과 트리 노드를 설명할 수 있다.

자주 하는 오해

  • P[i]는 A[i] 직전까지의 합이므로 오른쪽 끝 R을 포함하려면 P[R + 1]을 사용합니다.
  • 트리에서 부모의 합을 더했다면 그 자식의 합은 중복해서 더하지 않습니다.

핵심 정리

  • 누적합은 두 칸만 읽어 구간 합을 구합니다. 값이 바뀌면 그 값을 포함하는 뒤쪽 칸들을 갱신합니다.
  • 세그먼트 트리는 조회 범위를 겹치지 않는 노드로 덮고, 한 원소가 바뀌면 해당 리프의 조상만 다시 계산합니다.

학습 확인

문제 1

예제의 A[2]를 바꾸면 어느 누적합 칸부터 값이 바뀌나요?

문제 2

트리의 [2, 3] 구간이 조회 범위에 완전히 들어가면 다음에 무엇을 하나요?

핵심 단계

  1. 1

    누적합은 0에서 시작해 원소를 하나씩 더하고, 트리는 리프를 채운 뒤 아래에서 위로 합을 저장합니다.

  2. 2

    같은 [1, 6]을 누적합에서는 두 칸의 차이로 구하고, 트리에서는 완전히 포함된 구간들의 합으로 구합니다.

  3. 3

    A[2]를 바꿔 누적합의 뒤쪽 칸과 트리의 리프부터 루트까지 갱신합니다.

  4. 4

    갱신 후 같은 구간을 다시 조회해 두 방식의 결과를 비교합니다.

핵심 개념 및 실무 적용 분야

✓고정된 일별 방문자 배열에서 여러 기간의 방문자 합 조회
✓일별 기록이 수정되는 대시보드에서 임의 기간의 합 조회

참고 자료

개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.