분류

  • 구간 합 구하기 알고리즘

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def update(tree, i, dif):
    while i < len(tree):
        tree[i] += dif
        i += (i & -i)

def sum(tree, i):
    result = 0
    while i > 0:
        result += tree[i]
        i -= (i & -i)
    return result

def get_selection(tree, start, end):
    return sum(tree, end) - sum(tree, start - 1)

설명

배열에서 특정 구간의 합을 빠르게 구할 수 있는 알고리즘이다.

N개의 항목을 하나씩 더해서 구한다면 n만큼의 시간 복잡도가 필요하지만,

이 알고리즘을 이용하면 $logN$만에 구간 합을 구할 수 있다.

1에서 8까지 펜윅 트리 예시

https://i.ibb.co/PxJjk5K/2022-02-28-4-21-50.png

K & -K는 마지막 비트의 숫자를 구하는 비트마스킹 알고리즘이다. (예시)

8의 경우 마지막 비트는 8(・・・1000)로 1-8까지의 합으로 트리를 구성할 수 있다.

6의 경우 마지막 비트는 2(・・・0010)로 5-6까지의 합을 나타낸다.

복잡도

$O(logN)$

참고

https://m.blog.naver.com/ndb796/221312822103