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

Question

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

如果第一个操作的正确实现，我很确定第二个操作很容易解决。

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

这太慢了(在 python 中，C 不是一个选项)，我想不出一种方法来利用我的数据的固有结构来创建高效的 BST 合并操作。

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

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

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

Answer 1

据我了解，您的问题范围为 [A, B] 并且查询形式为 -

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

E.g.
R1 R2 C1
R3 R4 C2

1. Query a range for the total number of items in particular categories. E.g. find count of categories in R1 R4

A simple implementation using dictionaries as given above would not work as I describe by this example -

suppose we have a range [1000, 5000]

and we make assignment as follows -

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

Now we make the following assignment

1 5000 C5555

This will make updation/changes/deletion to previously assigned ranges of the ranges O(N) where N is maximum size of range (B - A)

D['category'] = set(of_all_the_ranges_you_have_in_category)

In this case deletion of previous ranges from corresponding sets in categories C1,C2...C4999 will be needed for last assignment ( 1 5000 C5555 )

OR

1 : { "stop" : 5, "category" : "C1"}, 6 : { "stop" : 19, "category" : "C23"},

Here updation of category for each starting value (1,2,3,4...,4999) will be required for last assignment ( 1 5000 C5555 )

A better option that will make updation of ranges in O(lg n) would be segment trees (http://en.wikipedia.org/wiki/Segment_tree )

For the above example the segment tree will look something like this

                   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，它的 child 现在将不会被更新(记住仅在需要或惰性传播时更新)。节点 5:5 的类别也将设置为 C1

3 4 C2

Query 会沿着树向 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。接下来它将设置 children_update 要求 3:4 为真，以便将来更新其子项(在这种情况下已经设置..没有伤害)。