Fenwick tree
Fenwick tree, 펜윅 트리라고 불리는 자료구조가 있다. binary indexed tree (BIT) 라고도 불린다.옛날에는 이 BIT라는 이름이, 펜윅 트리 말고 top-down 혹은 bottom-up 형식의 세그먼트 트리를 가리키기도 한 것 같은데, 요즘은 다들 이 펜윅 트리만 지칭하는 것 같다. 각각의 숫자는 인덱스(첨자)를 의미하고, 그 숫자와 연결된 흑색 사각형과 그 밑의 흰색 직사각형이 전부 해당 인덱스가 들고 있는 영역이다. 각각의 숫자가 나타내는 구간이 어떻게 결정되는지 알아보자. 12의 경우 이진수로 나타내면 1100 이다. 여기서 밑(제일 오른쪽)부터 쭉 올라가면서 가장 먼저(즉, 가장 오른쪽에서) 나타나는 1의 위치는 100 이다. 이를 LNZB(lowest nonzero b..
2013. 9. 2. 17:23