Binary-Indexed-Tree

#data-structure #tree

@ 참고 자료)

• 개발자 영맨 - [Range Sum] 구간 합 #2 - Binary Indexed Tree (Fenwick Tree)

1. Range Query - O(logn)

• 끝자리가 겹치지 않는다.
• sum(0,10) = BIT[0] + BIT[8] + BIT[10] + BIT[11]
  • 11 = 01011₂
  • 10 = 01010₂
  • 08 = 01000₂
  • 00 = 00000₂
• 이런 식으로 동작하도록 구현된 트리!

2. Point Update - O(logn)

• update(4, delta)
  • BIT[5] += delta // 5 = 00101₂ (-> + 1₂)
  • BIT[6] += delta // 6 = 00110₂ (-> + 10₂)
  • BIT[8] += delta // 8 = 01000₂

3. Range Update

TODO!

---

Last update: February 26, 2023
Created: February 8, 2023