algorithm - 桶的索引计数

Question

所以，这是我的小问题。

假设我有一个桶列表 a ₀ ... a _n分别包含 L <= c ₀ ... c _n < H 项目。我可以决定 L 和 H 的限制。我什至可以动态更新它们，尽管我认为这不会有太大帮助。

桶的顺序很重要。我不能去交换它们。

现在，我想索引这些存储桶，以便：

看起来很容易吧？看到这些标准，我立即想到了一棵芬威克树。这就是他们真正的意义所在。

但是，当您考虑用例时，会出现一些其他用例：

我还没有弄清楚如何有效地编辑 Fenwick 树：删除/添加节点而不重建整个树...

当然，我们可以设置 L = 0，这样删除就变得不必要了，但是添加项目并不能真正避免。

所以这是一个问题：

您是否知道该索引的更好结构或如何更新 Fenwick 树？

主要关注的是效率，因为我确实计划实现它缓存/内存考虑值得担心。

背景：

我正在尝试提出一种类似于 B-Trees 和 Ranked Skip Lists 但具有本地化索引的结构。这两种结构的问题是索引是沿着数据保存的，这在缓存方面效率低下（即您需要从内存中获取多个页面）。数据库实现表明，将索引与实际数据隔离开来对缓存更友好，因此效率更高。

score 3 · Accepted Answer

我将您的问题理解为：

每个存储桶都有一个内部顺序，而存储桶本身也有一个顺序，因此所有元素都有一些排序，您需要该排序中的第 i 个元素。

为了解决这个问题：

您可以做的是维护一个“累积值”树，其中叶节点 (x1, x2, ..., xn) 是存储桶的大小。节点的值是其直接子节点的值之和。保持 na 的 2 次方会使其变得简单（最后你总是可以用零大小的桶填充它），这棵树将是一棵完整的树。

对应于每个存储桶，您将维护一个指向相应叶节点的指针。

例如，假设桶大小为 2、1、4、8。

树看起来像

如果要总计数，请读取根节点的值。

如果你想修改一些xk（即改变相应的桶大小），你可以沿着父指针向上走，更新值。

例如，如果您将 4 个项目添加到第二个存储桶，它将是（标有 * 的节点是更改的节点）

     19*
    /   \
   7*    12
  / \   / \
 2  5*  4  8

如果你想找到第 i 个元素，你沿着上面的树走，有效地进行二分搜索。您已经有一个左孩子和右孩子计数。如果 i > 当前节点的左子节点值，则减去左子节点值并在右树中递归。如果 i <= 左子节点值，则向左并再次递归。

假设您想在上面的树中找到第 9 个元素：

因为根的左孩子是 7 < 9。你从 9 中减去 7（得到 2）然后向右走。

由于 2 < 4（12 的左孩子），你向左走。

你在第三个桶对应的叶子节点。您现在需要选择该存储桶中的第二个元素。

如果你必须添加一个新的桶，你可以通过添加一个新的根，使现有的树成为左子节点，并添加一个新的树，除了你添加的桶之外，你的树的大小都为 0（如果需要）。成为新树最左边的叶子）。这将分摊 O(1) 时间以向树添加新值。需要注意的是，您只能在末尾添加一个桶，而不能在中间的任何地方添加。

获得总计数是 O(1)。更新单个存储桶/查找项目是 O(logn)。

添加新桶的摊销时间为 O(1)。

空间使用量为 O(n)。

除了二叉树，您也可以使用 B-Tree 来做同样的事情。

score 0 · Accepted Answer

我仍然希望得到答案，但是根据建议，到目前为止，我可以提出以下@Moron建议。

显然我的小芬威克树的想法不容易适应。在 fenwick 树的末端添加新的桶很容易，但在中间却不是，所以这是一种失败的原因。

我们剩下 2 个数据结构：二叉索引树（讽刺的是 Fenwick 用来描述他的结构的名字）和排名跳过列表。

通常，这不会将数据与索引分开，但是我们可以通过以下方式获得此行为：

我更喜欢跳过列表而不是二叉树，因为它们是自组织的，所以我省去了不断重新平衡我的树的麻烦。

这些结构将允许到达中的第 i 个元素O(log N)，我不知道是否有可能获得更快的渐近性能。

另一个有趣的实现细节是我有一个指向该元素的指针，但其他元素可能已被插入/删除，我现在如何知道我的元素的等级？

如果存储桶指向拥有它的节点，这是可能的。但这意味着节点不应该移动，或者它应该在移动时更新存储桶的指针。

2 回答 2