Compact Fenwick trees for dynamic ranking and selection
Compact Fenwick trees for dynamic ranking and selection
Summary The Fenwick tree is a classical implicit data structure that stores an array in such a way that modifying an element, accessing an element, computing a prefix sum and performing a predecessor search on prefix sums all take logarithmic time. We introduce a number of variants which improve the …