algorithm - 桶的索引计数

Question

所以，这是我的小问题。

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

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

现在，我想为这些桶编制索引，以便:

• 我知道元素的总数
• 我可以查找第i个元素
• 我可以从任何桶中添加/删除项目并有效地更新索引

看起来很简单吧？看到这些标准，我立即想到了分域树。这就是它们的真正意义。

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

• 如果桶计数低于 L，则桶必须消失(暂时不要担心元素)
• 如果桶计数达到 H，则必须创建一个新桶，因为这个桶已满

我还没有想出如何有效地编辑 Fenwick 树:在不重建整棵树的情况下删除/添加一个节点...

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

问题来了:

您是否知道此索引的更好结构或如何更新分域树？

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

背景:

我正在尝试提出一种有点类似于 B 树和排名跳跃列表但具有本地化索引的结构。这两种结构的问题在于索引与数据保持一致，这在缓存方面效率低下(即您需要从内存中获取多个页面)。数据库实现表明，将索引与实际数据隔离开来对缓存更友好，因此效率更高。

Answer 1

我对你的问题的理解是:

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

要解决这个问题:

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

对应每一个bucket你都会维护一个指向对应叶子节点的指针。

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

这棵树看起来像

     15
    /  \
   3    12
  / \  / \
 2  1  4  8

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

如果你想修改一些 xk(即改变相应的桶大小)，你可以沿着父指针向上移动树，更新值。

例如，如果您向第二个存储桶添加 4 个项目，它将是(标有 * 的节点是发生变化的节点)

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

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

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

因为 root 的左 child 是 7 < 9。 你从 9 中减去 7(得到 2)然后向右走。

因为 2 < 4(12 的左 child )，你往左走。

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

如果你必须添加一个新的桶，你可以通过添加一个新的根来将你的树的大小加倍(如果需要的话)，使现有的树成为左子树并添加一棵除了你添加的桶之外所有桶都是零的新树(我们是新树最左边的叶子)。这将被摊销 O(1) 时间用于向树添加新值。需要注意的是，您只能在末尾添加一个桶，而不能在中间的任何地方添加。

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

添加新桶的时间复杂度为 O(1)。

空间使用量为 O(n)。

您可以用 B 树来代替二叉树。