개요 펜윅 트리(Fenwick Tree)라고도 한다. 누적 합 배열의 동적 자료구조이다. 이름은 트리이지만 배열로 표현한다. 모든 배열의 인덱스가 1부터 시작한다고 가정한다. 그래야 구현하기가 좀 더 쉽다. 시간복잡도가 O(log n)인 2가지 연산을 제공한다. update(int k, int diff) : 배열의 원소 갱신 sum(int k) : 1번 원소부터 k번 원소까지의 구간 합 계산 p(k) : k의 약수 중에서 가장 큰 2의 거듭제곱. p(k) = sum(k - p(k) + 1, k) 위치 k에서 끝나면서 그 길이가 p(k)인 구간의 합 BIT를 사용하면 어떤 sum(1, k)의 값도 O(log n)에 구할 수 있다. 배열의 원소를 갱신하면 BIT에서 해당 원소가 포함되어 있는 값도 갱신해야 ..