[알고리즘] 바이너리 인덱스 트리(BIT)

1. 바이너리 인덱스 트리

Binary Indexed Tree, BIT, 펜윅트리라고도 한다.

데이터 업데이트가 가능한 상황에서의 구간합을 구할 때 사용하는 자료구조이다.

2. 2진수로 표현 후 가장 마지막 비트의 값

일단 기본적으로 특정 수에 대한 negative값을 얻기 위해선, 2진수 비트에서 0과 1을 flip하고 마지막 비트에 +1을 한다(즉 2의 보수를 구한다).

이때 특정값 N에 대하여, N&-N 메소드를 이용하면, N을 2진수(비트)로 표현하였을때 가장 마지막 비트의 값을 도출할 수 있다.

for i in range(8+1):
    print((i&-i))

3. 바이너리 인덱스 트리의 과정

위 2진수 비트 표현을 이용하여 바이너리 인덱스 트리를 먼저 구현할 수 있다.

이때 각 배열에 해당하는 특정 수가 있을때, 각 수의 인덱싱과 해당 인덱스에 대한 i&-i(인덱스를 2진수로 표현하였을때 가장 마지막에 위치한 0이 아닌 비트값)에 주목한다.

위와 같이, 11번째 원소에 있는 값(숫자 11이 아님)까지의 누적 합을 구하고자 할 때는, 11번째 인덱스의 수를 1씩 빼면서 그 값을 누적시키는 과정을 진행한다. 그 과정이 바이너리 인덱스 트리 알고리즘의 과정이다.

이때 시간복잡도는 최대 O(logN)을 보장한다.

4. 위 과정을 활용하여 부분적으로 값이 바뀌는(업데이트) 상황에서 구간합 도출하기

N(1<=N<=1000K)개의 수가 있고, 중간에 수의 변경이 번번히 일어난다.
이 상황에서 어떤 부분수열의 합을 구하려고 한다.
데이터 변경횟수를 M(1<=M<=10K), 구간합 계산 횟수를 K(1<=K<=10K)라 하자.

이때 구간의 합을 구할 수 있는 알고리즘을 어떻게 구성할 수 있을까

구성하는 함수는 두가지이다.

• i번째 수까지 누적합 계산
• i번째 수를 특정값만큼 더할때

#데이터 업데이트가 가능한 상황에서의 구간합
#바이너리 인덱스 트리, BIT

import sys
#데이터 개수, 변경횟수, 구간 합 계산 횟수
n, m, k = map(int, sys.stdin.readline().split())

#전체 데이터와 인덱스 트리를 배열에 나타낸다.
#인덱스 1부터 연산하는 것에 유의
arr = [0] * (n+1)
tree = [0] * (n+1)

#i번째 수까지 누적 합을 계산하는 함수
def prefixSum(i):
    result = 0
    while i > 0:
        result = result + tree[i]
        #0이 아닌 마지막 비트만큼 빼가면서 이동
        i = i - (i&-i)
    return result

#i번째 수를 특정 값만큼 더할때(값 업데이트)
def update(i, dif):
    while i <= n:
        tree[i] = tree[i] + dif
        i = i + (i&-i)

#구간합
def intervalSum(start, end):
    return prefixSum(end) - prefixSum(start - 1)

#문제
for i in range(1, n + 1):
    x = int(sys.stdin.readline())
    arr[i] = x
    #부분 수열 업데이트
    update(i, x)

for i in range(m+k):
    a, b, c = map(int, sys.stdin.readline().split())
    # 업데이트 연산일 경우
    if a==1:
        update(b,c-arr[b]) #바뀐 크기를 적용
        arr[b] = c
    else: #구간합
        #b-left
        #c-right
        print(intervalSum(b,c))

5. 참조자료

이코테 2021 - 바이너리 인덱스 트리
https://www.youtube.com/watch?v=fg2iGP4e2mc&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=14