紧凑型 Fenwick 树在动态排序和选择中的应用 (arxiv.org)

Fenwick 树是一种经典的隐式数据结构，用于存储数组，支持高效地修改元素、访问元素、计算前缀和以及执行前缀和上的前驱搜索。本文介绍了Fenwick 树的几种变体，可以减小其在已知数组元素上限时的空间占用，并可以更快地执行前驱搜索。作者旨在使用这些变体来实现高效的动态位向量，该结构能够在对数时间内执行更新、排序和选择操作，并且空间开销仅为百分之几，优于现有的具有相同目的的数据结构。