大范围连续整数的数据结构？

Question

假设您在内存中有大量连续的整数,每个整数属于一个类别.两个操作必须是O(log n):将范围从一个类别移动到另一个类别,并查找给定范围的类别计数.

我很确定第二次操作是在第一次操作的正确实现的情况下解决的.

每个整数都从一个类别开始,所以我从一组平衡的BST开始.将子树从一个BST移动到另一个BST(例如,将范围移动到另一个类别)具有相当于合并两个BST的运行时间,即O(n1*n2)[ 1 ].

这太慢了(在python中,C不是一个选项),我无法找到一种方法来利用我的数据的固有结构来创建一个有效的BST合并操作.

我现在正在研究AVL,红黑和间隔树,二进制堆和treaps.比较他们的属性是压倒性的.我应该使用哪种结构？

编辑(问题澄清):我对如何存储这些值并创建数据结构很灵活.关于我如何接收来自其他应用程序的输入,我不灵活,如下所示:CATEGORY(cat3, I, J).我当前的解决方案创建了一个树,其中包含该范围中每个整数的节点.这对于我的数据集的大小来说太慢了,所以如果给出更好的方法,我很乐意重新设计.

任何给定的请求都可以将任何可能的整数范围移动到任何类别中.换句话说,范围在CATEGORY(cat1, 1, 10)后面的意义上是重叠的CATEGORY(cat3, 5, 15),但是在任何给定时间每个整数将恰好属于一个类别的意义上是非重叠的.

Answer 1

据我理解，你有一个范围 [A，B] 和以下形式的查询 -

1. 将特定范围分配给类别

例如
R1 R2 C1
R3 R4 C2

1. 查询特定类别中项目总数的范围。例如查找 R1 R4 中的类别数

使用上面给出的字典的简单实现不会像我在这个例子中描述的那样工作 -

假设我们有一个范围 [1000, 5000]

我们的分配如下 -

1 2 C1
2 3 C2
3 4 C3
......
4999 5000 C4999

现在我们进行以下分配

1 5000 C5555

这将对之前分配的范围 O(N) 进行更新/更改/删除，其中 N 是范围的最大大小 (B - A)

D['类别'] = set(of_all_the_ranges_you_have_in_category)

在这种情况下，最后一次分配需要从类别 C1、C2...C4999 中的相应集合中删除先前的范围 ( 1 5000 C5555 )

或者

1：{“停止”：5，“类别”：“C1”}，6：{“停止”：19，“类别”：“C23”}，

此处，最后一次分配 ( 1 5000 C5555 ) 需要更新每个起始值 (1,2,3,4...,4999) 的类别

在 O(lg n) 中更新范围的更好选择是线段树（http://en.wikipedia.org/wiki/Segment_tree）

对于上面的例子，线段树看起来像这样

                   1000:5000
                      |
             ---------------------
             |                   |
           1000:3000         3001:5000
            |                    |
    ----------------      --------------------
   |               |      |                  |
 1000:2000     2001:3000   3001:4000       4001:5000

...................................................... …………………………………… ............................ 等等

叶节点将具有范围（1:2、2:3，...）

您可以为每个节点分配一个值“类别”，并给定一个区间，遍历树并适当划分区间（例如，对于 2500 到 4500，划分为 2500:3000 和 3001:4500，并在两个方向上进行，直到找到具有匹配范围的节点） 。

现在有趣的事情是在需要时更新节点的子节点。例如，在执行 1 5000 C5555 等作业时，不要立即继续更新子级。这个东西称为延迟传播，您可以在这里了解更多信息（http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296）。

现在进行查询部分。如果类别数量非常少，您可以在每个节点维护一个频率表，并在需要时更新范围，并在需要时延迟传播，否则，您将不得不从叶子到节点遍历整个树，计数和复杂度将变为 O （n）。

我认为可能存在更好的查询解决方案。我没有想到这一点。

更新 让我们举一个小例子。

范围 [1,8]

允许的类别 {C1, C2}

        1:8
     1:4         5:8
     1:2  3:4      5:6    7:8
 1:1 2:2 3:3 4:4  5:5 6:6 7:7 8:8

每个节点将有3个字段[category,category_counts[],children_update_required = false]

1 5 C1

查询将被划分，节点 1:4 的类别将设置为 C1，children_update_required 将设置为 true，其子节点现在不会更新（记住仅在需要时更新或延迟传播）。另外，节点 5:5 的类别将设置为 C1

3 4 C2

查询将沿着树向 3:4 传播（在到达 3:4 的过程中，1:2 和 3:4 的类别将更新为 C1，1:4 的 Children_update_required 将设置为 false，1:2 和 3 :4的children_update_required将被设置为true），现在将根据当前要求将3:4的类别更新为C2。接下来，它会将 3:4 所需的 Children_update 设置为 true，以便将来更新其子级（在本例中已经设置了..不会造成任何损害）。