[자료구조] 펜윅 트리 (Fenwick Tree) - Binary Indexed Tree

목 차 펜윅 트리(Fenwick Tree) 펜윅 트리와 세그먼트 트리 펜윅 트리를 구현하며 배운 것들 구현 방법 펜윅 트리(Fenwick Tree) Binary Indexed Tree 라고도 불리는 펜윅트리는 수열의 특정 구간의 합을 빠르게 계산하고, 요소를 빠르게 변경 할 수 있는 자료구조 이다. 특징 시간 복잡도: update 와 sum 메서드 모두 O(log n)의 시간 복잡도를 가진다. 공간 복잡도: O(n) 만큼의 공간을 사용한다. 작동 원리 SUM 함수: 구간 합을 구하는 함수 UPDATE 함수: 특정 요소가 변경되면 그 요소에 영향을 받는 인덱스를 타고 올라가며 변경한다. 펜윅 트리와 세그먼트 트리 세그먼트 트리 펜윅 트리 구조 이진 트리 기반 배열 기반 시간 복잡도 업데이트 & 구간 합 모..

Algorithm 2023.12.06