Fenwick Tree || Binary Indexed Tree 에 관한 정보를 어디서 얻을 수 있을까요?

canuyes의 이미지

공부 도중에 Fenwick Tree(Binary Indexed Tree 라고도 불리는)에 대해 알게 되었습니다.
이 자료구조에 구글링 해보았지만 아래 탑코더에 나와 있는 정보가 다네요 ㅠㅠ.

[링크](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees)
하지만 위 링크의 글이 잘 이해 되지 않네요 ㅠㅠ.

듣기로는 BIT가 아래의 연산 2개를 O(logn)에 수행 한다고 들었는데,

1. 박스 i에 데이터 추가.
2. 박스 i 부터 k까지의 합 반환.

위의 리퍼만 봐서는 감을 잡기가 힘듭니다.
BIT가 잘 설명되어 있는 책 또는 사이트가 있을까요?

익명 사용자의 이미지

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917
위키 페이지의 자료중 하나.
당사자가 쓴 글같네요

canuyes의 이미지

쭉 읽어보고나서 잘 해결 했습니다 ^^