3 个不稳定版本
| 0.2.0 | 2022年6月19日 |
|---|---|
| 0.1.1 | 2022年6月15日 |
| 0.1.0 | 2022年6月14日 |
#1212 in 数据结构
47KB
775 行
Fenny
Fenny 是一个 Fenwick 树（也称为二叉索引树，BIT）库。它们是一种数据结构，可以高效（即 O(log n)）支持三种操作。
a[i] += v;
a[..=i].iter().sum();
第三种操作是前缀和的二分查找。
以下是一个简单的使用示例
let mut tree = [0; 13]; // An array of zeros is a fenwick tree of zeros.
fenny::update(&mut tree, 2 /* 0-based index */, 7);
fenny::update(&mut tree, 5, 20);
fenny::psum(&tree, 2); // Returns 7.
fenny::psum(&tree, 5); // Returns 27.
let root_p1 = fenny::get_root_p1(tree.len());
// Returns Some(5), as a[..=5].iter().sum() == 7 + 20 > 26.
fenny::first_larger(&tree, root_p1, 26);
fenny::first_larger(&tree, root_p1, 27); // Returns None.
斜率偏移量
什么比 Fenwick 树更好？当然是有两个！如果我们再加入另一棵树，我们就可以支持一个额外的操作，范围更新。同样，在相同的 O(log n) 时间内。范围的大小无关紧要，它可以像更新单个元素一样更新整个数组。
let mut slope = [0i64; 13];
let mut offset = [0i64; 13];
// Conceptually a[2..=5] += 3;
fenny::update_so(&mut slope, &mut offset, 2..=5, 3);
fenny::psum_so(&slope, &offset, 2); // Returns 3.
fenny::psum_so(&slope, &offset, 3); // Returns 6.
let root_p1 = fenny::get_root_p1(slope.len());
fenny::first_larger_so(&slope, &offset, root_p1, 3); // 3.
高维
这存在于 2d 和 3d 中。 psum_2d(&tree, p) 计算满足 (q.y <= p.y && q.x <= p.x) 的所有点 q 的和。
use fenny::*;
let dim = Dim2{y: 5, x: 8};
let mut tree = vec![0; dim.y * dim.x];
update_2d(&mut tree, dim , Point2{y: 3, x: 6}, 7);
// Returns 0
psum_2d(&tree, dim, Point2{y: 2, x: 6});
// Returns 0
psum_2d(&tree, dim, Point2{y: 3, x: 5});
// Returns 7
psum_2d(&tree, dim, Point2{y: 3, x: 6});
// Returns 7
psum_2d(&tree, dim, Point2{y: 4, x: 7});
这些操作在 log(dim.x) * log (dim.y) * log (dim.z) 内运行
高维，斜率偏移，字典序
首先有一些背景知识。这是我为了帮助算术编码而想出来的。我们在一个离散空间上有概率密度函数。现在为了将其转换为高效的编码，我们需要将我们的空间映射到 [0, 1)，其中每个单元格对应一个长度与它的概率成比例的段。所以，让我们想象我们将所有单元格排列成一行，然后计算概率的前缀和。这将给我们带来段！
好的，但有一个问题。我们希望高效地操作细胞在三维空间中的概率。具体来说，我们希望选择一个以（x0，y0，z0）和（x1，y1，z1）为顶点的盒子，并一次性增加该盒子内所有细胞的权重。我们可以在一维中使用斜率-偏移构造进行范围更新，那么三维空间中有没有类似的方法呢？是的，有！通过每个维度一个斜率，我们可以实现我们的目标！这类似于Mishra的一个算法（链接），但我们可以通过只支持字典序查询而不是任意盒子来稍微降低成本。在解码步骤中，需要将[0, 1)区间的数转换为相应的细胞。这可以通过使用first_larger函数族来完成。
背景介绍完毕，让我们看看这些操作。
use fenny::*;
let dim = Dim3{z: 12, y: 6, x: 8};
let mut slope_z = vec![0i64; dim.z];
let mut slope_y = vec![0i64; dim.z * dim.y];
let mut slope_x = vec![0i64; dim.z * dim.y * dim.x];
let mut offset = vec![0i64; dim.z * dim.y * dim.x];
let p0 = Point3{z: 3, y: 2, x: 1};
let p1 = Point3{z: 7, y: 5, x: 5};
let p2 = Point3{z: 4, y: 0, x: 0};
// Updates all points q with p0.x<=q.x<=p1.x && p0.y<=q.x<=p1.y && p0.z<=q.x<=p1.z
update_so_3d_lex(&mut slope_z, &mut slope_y, &mut slope_x, &mut offset, dim, p0, p1, 11);
// Our points out are laid out in lexicographic order according to z, y, x.
// Since 4, 0, 0 comes after (3, 2, 1), (3, 2, 2), ... (3, 5, 5) our result is 5 * 4 * 11;
psum_so_3d_lex(&slope_z, &slope_y, &slope_x, &offset, dim, p2);
// (4, 0, 0) has a psum of 5*4*11, but so does (3, 5, 5), so that's the result.
first_larger_so_3d_lex(&slope_z, &slope_y, &slope_x, &offset, dim, 5 * 4 * 11 - 1);
这些操作在 log(dim.x) * log (dim.y) * log (dim.z) 内运行
致谢
我找到了一篇由boba5551撰写的topcoder 文章，对理解Fenwick树非常有帮助。图示很棒。
wikipedia 文章提供了很好的概述以及如何使用两个结合树进行范围更新的有用信息。
fenwick rust库编写得很好，并且是一个灵感来源。