February 18, 2023

I recently came across some Racket code on Reddit that implements Fenwick trees, aka binary indexed trees (BIT). Fenwick’s article, which is not the original paper on that particular data structure, A New Data Structure for Cumulative Frequency Tables (PDF) explains all the details, but there’s also a nice tutorial, as well as some applications for competitive programming.