[**Fenwick tree**][wiki] 或 **binary indexed tree**/**bit indexed tree** 是一种数据结构
它有效地支持对数字数组“a [0..n]”的以下两个操作:
- 计算前缀和:`a[0] + a[1] + ... + a[i]`
- 更新一个元素:`a[i] += delta`
使用简单的实现,只能使其中一个操作具有恒定的时间
复杂性,而另一个必须是线性的。对于 Fenwick 树,两者都只需要 `O(log(N))`。
2022-06-12 14:05:10
8KB
算法
rust