Deconstructing Fenwick Trees with Functional Programming

This paper delves into the implementation of Fenwick trees (also known as binary indexed trees). Starting with the more readily understandable segment tree, the author uses functional programming and equational reasoning to derive the implementation of Fenwick trees, revealing the logic behind their seemingly mysterious bitwise operations. By cleverly using a Haskell EDSL to operate on infinite two's complement binary numbers, the paper ultimately explains the secret of Fenwick trees' efficient implementation and proves the logarithmic time complexity of its update and range query operations.