Fenwick Tree (Binary Indexed Tree, 이진인덱스 트리)

√ 펜윅 트리란?

 

Data structure that supports sum range queries as well as setting values in a static array and getting the value of the *prefix sum up some index efficiently

 

>> 위키백과의 설명을 빌리자면, 요소 업데이트와 접두사의 합계 계산을 효과적으로 수행하도록 하는 트리를 의미합니다

 

 

** 구간합 Prefix sum (Cumulative sum, inclusinve sum, inclusive scan)

Prefix sum이 감이 잘 안와서 찾아봤는데요, 일반적으로 생각하면 이런 누계합을 의미하는데요
computer science 알고리즘과 functional programming language에서 중요한 역할을 한다고 합니다

https://en.wikipedia.org/wiki/Prefix_sum

 

https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

백준 온라인 펜윅트리 설명 링크

백준 웹사이트에서 설명을 잘 적어주셔서 가지고 와봤는데요

 

1에서 16까지의 수가 하얀색 박스라면, 각 숫자를 이진법으로 나타났을 때 마지막 1이 나타내는 수를 회색으로 표현했을 때 그 밑의 연두 박스는 i번째 숫자에서 L[i]가 커버하는 구간을 나타냅니다

 

백준

 

그렇다면 하나의 L[I] = i & -i 로 이해할 수 있는데요

 

만약, A가 [3,2,5,7....] 회색 박스에 있다면 TREE[I]의 값은 아래 연두색 박스와 같게 됩니다

A[12]에서 내려오면 전체 20트리박스에 A[9] + A[10] + A[11] + A[12]가 저장되어 있음을 알 수 있습니다

 

백준

 

아래는 백준코드의 예시 문제인데요

위의 개념처럼 각 A[1]에서 A[13]까지 이진수로 나타낸 값의 마지막 1의 위치를 빼면서 전체 합을 구 할 수 있습니다

 

int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= (i & -i);
    }
    return ans;
}
#백준코드 예시코드

 

 

√ 펜윅 트리 Time Complexity

Construction	O(n)
Point Update	O(log(n))
Range Sum	O(log(n))
Range Update	O(log(n))
Adding Index	N/A
Removing index	N/A

 

 

Range query Algorithm

 

https://www.youtube.com/watch?v=RBSGKlAvoiM&t=20737s&ab_channel=freeCodeCamp.org

 

 

 

 

**개념이 복잡하지만 추가적인 관련 코딩 문제를 찾으면 업데이트 하겠습니다

 

 

 

 

 

Source:

https://www.youtube.com/watch?v=RBSGKlAvoiM&t=20737s&ab_channel=freeCodeCamp.org 

https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)