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