Fenwick(Binary Indexed Tree) 에 대해서..

잊어 버릴만 하면 나오는 문제 때문에, 계속 찾아보게 되어서 정리해 본다.
아, 그리고 이 사이트는 참고가 많이 된다.

https://tempdev.tistory.com/20

• Binary Indexed Tree 기본 형태

class BinaryIndexTree:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0 for _ in range(n+1)]
    
    def _update(self, idx: int, val:int):
        while idx <= self.n:
            self.tree[idx] += val
            idx += (idx & (-idx)) # +LSB(Least Significant Byte)
    
    def query(self, idx:int):
        t_sum = 0
        while idx > 0:
            t_sum += self.tree[idx]
            idx -= (idx & (-idx))
        return t_sum