_04.algorithm_binary_index_tree

Binary index Tree

• 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조
• 다른 이름으로 fenwick tree라고도 함

정수에 따른 2진수 표기

정수	2진수 표기
7	00000000 00000000 00000000 00000111
-7	11111111 11111111 11111111 11111001

• 0이 아닌 마지막 미트를 찾는 방법
  • 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해선 K & -K 계산하면 됨

• K & -K 계산 결과 예시

정수 K	2진수 표기	K & -K
0	00000000 00000000 00000000 00000000	0
1	00000000 00000000 00000000 00000001	1
2	00000000 00000000 00000000 00000010	2
3	00000000 00000000 00000000 00000011	1
4	00000000 00000000 00000000 00000100	4
5	00000000 00000000 00000000 00000101	1
6	00000000 00000000 00000000 00000110	2
7	00000000 00000000 00000000 00000111	1
8	00000000 00000000 00000000 00001000	8

n = 8
for i in range(n+1):
    print(i, "의 마지막 비트:", (i & -i))

• 트리 구조 만들기: 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수
• 특정 값을 변경할 때 : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값을 변경
• 1부터 N까지 누적 합 구하기: 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합 계산