[이코테]바이너리 인덱스 트리

Coding Test 14

이코테 14

1. 바이너리 인덱스 트리

• 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조

• 정수에 따른 2진수 표기

  7 | 00000000 00000000 00000000 0000111
  -7 | 11111111 11111111 11111111 1111001
  반대로 바꾸고 1을 더함

• 0이 아닌 마지막 비트 찾는 방법 K & -K를 계산

2. 트리 구조 만들기

0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수
13 = 1101 ->
A[1] + … + A[13] = Tree[1101] + Tree[1100] + Tree[1000]
(뒤에서 부터 1 하나씩 뺌)