Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고도 한다.
Fenwick Tree를 구하려면, 어떤 수 X를 이진수로 나타내었을 때, 마지막 1의 위치를 알아야 한다.
...
여기서 수 $i$에 대하여 이진수로 변환하였을 때 마지막에 존재하는 1이 나타내는 값을 $L[i]$라고 표현하자.
...
어떤 수 $N$개를 $A[1],..., A[N]$으로 표현했을 때, Tree[i]에는 $A[i]$ 부터 이전 $L[i]$개 만큼의 원소의 합이 저장된다.
여기서 $L[i] = -i\,\&\ i$ 로 구할 수 있다.