ftree

一个纯Rust（无依赖，no-std）的Fenwick树，用于高效计算动态前缀和。

背景

你是否曾经需要同时跟踪和更新一个总和？

假设你有一个表示其他容器长度的数组：[1, 6, 3, 9, 2]

如果你想获取到第n个元素的总和，最坏的情况下需要O(n)的时间。而更新操作则是简单地增量指定索引，O(1)的时间复杂度。

Fenwick树允许你在O(log n)的时间内同时获取总和和执行更新。

此外，假设你想获取第一个值小于等于总和的索引。

不使用Fenwick树，这需要(n * log n)的时间（在每次迭代中计算总和的二分查找）。然而，使用Fenwick树只需要O(log n)的时间。这可能看起来是一个非常狭窄的需求，但它确实是。它在indexset crate，一个两级的B-Tree中，用于非常高效地支持基于位置的向量索引。

性能

它的性能非常好。我已经在codeforces上找到了所有的竞争编程Fenwick树性能技巧，并将它们都放到了这个crate中。

命名

这个库被命名为 ftree，因为基本数据结构是 FenwickTree。

变更日志

见 CHANGELOG.md。