구간합 (Feat. Prefix Sum, Binary Indexed Tree)

  • 2022/06/03
  • 4-minute read

참고 원본 - 바이너리 인덱스 트리 10분 정복

BOJ 2042 구간 합 구하기 문제

Table of Contents

구간 합

  • 연속적으로 나열된 N개의 수에 대해, 특정 구간의 모든 수를 합한 값을 계산하는 문제
  • 이와 같은 문제를 해결하는 알고리즘으로 접두사 합(Prefix Sum) 방법이 있다

접두사 합?

  • 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해놓는 방법을 의미
  1. 합을 계산할 배열을 입력 받기 (arr)
  2. 입력 받은 배열을 이용하여, N까지의 합을 미리 계산 (prefix_sum)
  3. Left ~ Right까지의 합을 필요로 한다면, prefix_sum[Right] - prefix_sum[Left - 1]을 이용하여 계산
arr = [None]
arr += (list(map(int, input().split())))
print(arr)
prefix_sum = [0] * (len(arr))
for i in range(1, len(arr)):
    prefix_sum[i] = prefix_sum[i - 1] + arr[i]

left, right = map(int, input().split())\

print(prefix_sum[right] - prefix_sum[left - 1])
list 0 1 2 3 4 5
arr - 1 3 5 7 9
prefix_sum 0 1 4 9 16 25
  • 이와 같은 접두사 합은 입력된 배열이 고정되어 있을 때 아주 유용하게 사용할 수 있다.
  • 하지만 중간에 값이 바뀐다면…?, 그 때 마다 새롭게 합을 계산해야하므로, 처리가 생각보다 불편할 것으로 보인다.
  • 이와 같은 문제를 해결하려면 어떻게 해야할까…?

Binary Indexed Tree / Penwick Tree

  • 위와 같은 문제를 해결하기 위해 등장한 것이 Binary Indexed Tree / Penwick Tree이다.
  • 구간 합 문제에서 중간 중간 데이터의 변경이 빈번하게 일어나는 경우를 해결하기 위한 방법이라고 이해하면 좋을 것 같다.
  • 이진법의 구조를 활용하여, 구간 합 문제를 효율적으로 해결하는 자료구조를 의미
  • 0이 아닌 마지막 비트를 찾아서 계산에 사용하는 것이 핵심! (사용 방법은 뒤에 설명)
  • ex) 7 $\rightarrow$ 00000111 $\rightarrow$ 1의 자리가 마지막 비트
  • ex) 8 $\rightarrow$ 00001000 $\rightarrow$ 8의 자리가 마지막 비트
  • $K&(-K)$의 연산을 이용하면 빠르게 0이 아닌 마지막 비트를 찾을 수 있음
  • ex) 0000111 & 1111001 = 0000001 (1)
  • ex) 0001000 & 1111000 = 0001000 (8)
  • Binary Indexed Tree 구조
    • 구간합을 계산해야하는 배열 or 리스트 arr(1번 인덱스부터 시작) 에 대해 아래와 같은 연산을 수행
    • BIT[K] $\rightarrow$ $K$에서 시작하여 아래로 $K&(-K)$개의 합을 저장
    • ex) BIT[1] $\rightarrow$ 1에서 시작하여, 1개의 합을 저장 (arr[1]만 저장)
    • ex) BIT[2] $\rightarrow$ 2에서 시작하여, 아래로 2개의 합을 저장 (arr[2] ~ arr[1]의 합 저장)
    • ex) BIT[8] $\rightarrow$ 8에서 시작하여, 아래로 8개의 합을 저장 (arr[8] ~ arr[1]의 합 저장) BIT
  • 활용 방법
    • 특정 위치의 값만 바꿨을 때
    • arr[N]의 값을 바꿨을 경우, N번 째, M = N + (N & -N)번 째, K = M + (M & -M)번 째, 순으로 증가하며 바꿔주면 모두 교체가 가능하다. (인덱스 초과전까지 반복)
    • ex) arr[3]의 값을 바꾸면, 3번 째, 4 = 3 + (3 & -3)번 째, 8 = 4 + (4 & -4)번 째 … 순으로 모두 교체 BIT Change
    • 1번에서 N번째까지의 합을 구할 때
    • N번째까지의 합을 구할 때는 반대로, N번 째 값, M = N - (N & -N)번 째, K = M - (M & -M)번 째 순으로 감소하며 더해주면 1번부터 N번까지의 합을 구할 수 있다. (인덱스 1 미만까지 반복)
    • ex) 11번까지의 합, 11번 째, 10 = 11 - (11 & -11)번 째, 8 = 10 - (10 & -10)번 째까지의 합을 이용하면 11번까지의 합을 구할 수 있다. BIT sum
  • 구현 (BOJ 2042 문제 해답)
import sys
input = sys.stdin.readline
# 데이터 개수 n, 변경 횟수 m, 구간 합 계산 횟수 k
n, m, k = map(int, input().split())
arr = [0] * (n + 1) # 1번부터 사용 예정
BIT = [0] * (n + 1) # 1번부터 사용 예정

def prefix_sum(i):
    result = 0
    while i > 0:
        result += BIT[i]
        i -= (i & -i)
    return result

def update(i, difference): # 기존 값과의 차이를 입력
    while i <= n:
        BIT[i] += difference
        i += (i & -i)

def interval_sum(left, right):
    return prefix_sum(right) - prefix_sum(left - 1)

for i in range(1, n + 1):
    x = int(input())
    arr[i] = x # 값을 데이터에 넣은 후
    update(i, x) # BIT도 업데이트

for i in range(m + k):
    a, b, c = map(int, input().split())
    if a == 1: # 값을 변경할 때
        update(b, c - arr[b])
        arr[b] = c
    elif a == 2: # 구간 합을 계산할 때
        print(interval_sum(b, c))
    else: # 입력 오류
        print("입력이 잘못되었습니다, 1 또는 2를 넣어야합니다.")

Review

  • 여태 본 알고리즘 중에 제일 신기했던 것 같다.
  • 아이디어를 어디서 얻었는지… 진짜 대단한 사람…
  • 실제 활용은 어떤 경우에 필요할진 잘 모르겠지만, 아이디어가 진짜 신기해서 오래 기억날 것 같다.

comments