[자료구조] 인덱스 트리

트리구조로 구간 합 구하기

• 세그먼트 트리는 구현하는 과정이 복잡하고 어려움 → 인덱스 트리는 구현이 매우 간단하며 O(logN)의 시간 복잡도를 가짐
• 인덱스 트리는 세그먼트 트리에 비해 메모리 효율성이 높음

 

1. 특정 숫자의 마지막 비트를 구함(A & -A)
2. 각 인덱스의 마지막 비트를 내가 저장하고 있는 값들의 개수로 계산
3. 마지막 비트만큼 구간을 앞으로 이동하며 합을 구함

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수