펜윅 트리(바이너리 인덱스 트리) 시간복잡도 O(MlogN) 구간합, 값 업데이트O(logN) 그림1. 세그먼트 트리 그림2. 펜윅 트리 Fenwick Tree를 구현하려면 어떤 수 X를 이진수로 나타냈을 때 마지막 1의 위치를 알아야 합니다. 마지막 1이 나타내는 값을 L[i]라고 표기하면 L[3]은 11(2)로 1, L(10)은 1010(2)로 2 가 됩니다. 수 N개를 A[1] ~ A[N] 이라고 했을 때, Tree[i]는 A[i] 부터 앞으로 L[i] 개의 합이 저장되어 있습니다. 아래 그림은 각각의 i에 대해서, L[i]를 나타낸 표입니다. 아래 초록 네모는 i부터 앞으로 L[i]개가 나타내는 구간입니다. L[i] = i & -i가 됩니다. 그 이유는 아래와 같습니다. -num = ~num + ..