함수형 프로그래밍을 이용한 Fenwick 트리 분석

본 논문은 Fenwick 트리(이진 색인 트리라고도 함)의 구현 원리를 심도 있게 다룹니다. 이해하기 쉬운 세그먼트 트리로부터 시작하여 함수형 프로그래밍과 등식 추론을 사용하여 Fenwick 트리 구현을 단계적으로 유도하고, 겉보기에는 수수께끼 같은 비트 연산의 이면에 있는 논리를 밝힙니다. 무한 이진 보수 이진수에 작용하는 Haskell EDSL을 교묘하게 사용함으로써, 마침내 Fenwick 트리의 효율적인 구현 비밀을 밝혀내고, 업데이트 및 범위 쿼리 연산의 로그 시간 복잡도를 증명합니다.