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

假设内存中有大量连续整数，每个整数都属于一个类别。两个操作必须是 O(log n)：将范围从一个类别移动到另一个类别，以及查找给定范围的类别计数。

我很确定只要第一个操作的正确实现，第二个操作就可以轻松解决。

每个整数都从一个类别开始，因此我从一组平衡的 BST 开始。将子树从一个 BST 移动到另一个（例如，将范围移动到不同类别）的运行时间相当于合并两个 BST，即 O(n1 * n2)[1 https://stackoverflow.com/questions/1008513/how-to-merge-two-bsts-efficiently].

这太慢了（在 python 中，C 不是一个选项），而且我无法找到一种方法来利用数据的固有结构来创建高效的 BST 合并操作。

我现在正在研究 AVL、红黑树、区间树、二叉堆和 Treap。比较它们的特性是压倒性的。我应该使用哪种结构？

编辑（问题澄清）：我可以灵活地存储这些值并创建数据结构。我对如何接收来自另一个应用程序的输入不灵活，如下所示：CATEGORY(cat3, I, J)。我当前的解决方案为该范围内的每个整数创建一个带有节点的树。对于我的数据集的大小来说，这太慢了，所以如果有更好的方法，我很乐意重新架构。

任何给定的请求都可以将任何可能的整数范围移至任何类别。换句话说，范围在某种意义上是重叠的CATEGORY(cat1, 1, 10)其次是CATEGORY(cat3, 5, 15)，但非重叠是指每个整数在任何给定时间都恰好属于一个类别。

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

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

E.g.
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 )

OR

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

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

在 O(lg n) 内更新范围的更好选择是线段树 (http://en.wikipedia.org/wiki/Segment_tree 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 等作业时，不要立即继续更新子级。这个东西叫做惰性传播，你可以在这里了解更多信息（ ).

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

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

UPDATE让我们举一个小例子。

范围 [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，以便将来更新其子级（在本例中已经设置了..不会造成任何损害）。