BIT - 펜윅 트리

Binary Indexed Tree, BIT

고정된 배열의 구간합을 계산할 때 누적합 알고리즘은 사용하면 O(n)안에 해결가능하다.
하지만 지속적으로 값이 변동되는 백만개 배열의 구간합을 만번이상 수정과 합을 번갈아서 하면 매우 긴 시간이 걸린다.
비트 연산자를 이용해서 특정 구간만 미리 계산 및 업데이트를 하면 O(logN)으로 처리가능하다.
삽입하려는 데이터의 양수와 음수의 AND연산으로 인덱스의 마지막 비트위치를 알 수 있다.

curr_idx & -curr_idx

이 방법을 이용해서 변경하거나 삽입하려는 첫번째 인덱스에 접근하여 값을 업데이트하고 반복문을 통해
마지막 비트의 크기만큼 기존 인덱스에 추가해서 다음 인덱스에 값을 업데이트한다.
다음은 2번인덱스를 수정하는 예시.

구간합을 구할 때는 반대로 반복문을 돌면서 마지막 비트의 크기만큼 인덱스를 마이너스하여 방문한 노드들의 데이터를 합산한다.

이렇게 위 이미지 처럼 7번 인덱스까지의 누적합을 구할 수 있다.

실습해보기

https://www.acmicpc.net/problem/2042

import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())
bit = [0] * (n + 1)
l = [0]

def init_bit(pos,y):
    while 1:
        bit[pos] += y 
        last = pos & -pos
        pos += last
        if pos > n:
            break

def update_bit(pos,y):
    gap = y - l[pos]
    while 1:
        bit[pos] += gap
        last = pos & -pos
        pos += last
        if pos > n:
            break

def get_bit(pos):
    acc = 0
    while 1:
        acc += bit[pos]
        last = pos & -pos
        pos -= last
        if pos < 1:
            break
    return acc

for i in range(1, n + 1):
    x = int(input())
    init_bit(i,x)
    l += [x]

for i in range(m + k):
    a,b,c = map(int,input().split())
    if a == 1:
        update_bit(b,c)
        l[b] = c
    elif a == 2:
        print(get_bit(c) - get_bit(b - 1))