[Data Structure] Binary Indexed Tree

오늘은 Binary Indexed Tree 를 정리해볼까 한다. 나만을 위한. 나를 위한 정리다.

Binary Indexed Tree의 존재 이유는 부모노드가 자식노드들을 대표할 수 있게 하기 위함인데 자식들의 합이 부모노드가 된다. 예를 들어 방대한 수의 배열이 있을 때 그것들을 다 더하다가 시간이 다 지나는 경우에 쓰기 적합하다. 최솟값, 최댓값도 적용 가능한 대표적인 예다.

Binary 라는 이름이 붙은 것 답게 부모 노드는 자식 노드를 오직 2개만 갖게 된다.
기본적인 개념은 아래와 같다.





검색 하다보니 정말 잘 정리된 사이트를 찾았다.

https://www.acmicpc.net/blog/view/21
위의 설명을 손으로 따라간 흔적을 여기에 남긴다.

해당 블로그에 있는 코드

#include <cstdio> #include <vector> using namespace std; long long sum(vector<long long> &tree, int i) { long long ans = 0; while (i > 0) { ans += tree[i]; i -= (i & -i); } return ans; } void update(vector<long long> &tree, int i, long long diff) { while (i < tree.size()) { tree[i] += diff; i += (i & -i); } }