Dot Algo∙ DS/알고리즘 개념
2022. 1. 3.
[알고리즘] 펜윅 트리(Fenwick Tree) 빠르고 간단한 구간 합 구하기 (Java)
펜윅 트리(Fenwick Tree) : 빠르고 간단한 구간 합 세그먼트 트리의 가장 흔한 사용 예는 바로 구간 합을 빠르게 구하는 것이다. 이 경우 세그먼트 트리 대신 쓸 수 있는 세그먼트 트리의 궁극적인 진화 형태로 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree)라고 불리는 것이 있다. 펜윅 트리가 사용하는 중요한 아이디어는 구간 합 대신 부분 합만을 빠르게 계산할 수 있는 자료구조로 만들어도 구간 합을 계산할 수 있다는 것이다. arr[]의 위치 pos에 대해 배열의 부분합 psum[pos] = arr[0] + arr[1] + ··· + a[pos]를 빠르게 계산할 수 있다고 하자. 그러면 [i, j] 구간의 합은 psum[j] - psum[i-1]로 ..
![[알고리즘] 펜윅 트리(Fenwick Tree) 빠르고 간단한 구간 합 구하기 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/p4ZgT/btrpzLysrer/EC070o5DSAJkuhnyFz3cK0/img.png)