处理大范围连续整数的数据结构？
假设你在内存中有一大堆连续的整数，每个整数都属于一个特定的类别。你需要进行两种操作，这两种操作的时间复杂度都要达到O(log n)：一种是把一段整数从一个类别移动到另一个类别，另一种是查找某个范围内各类别的数量。
我觉得只要第一种操作实现得当，第二种操作就能很简单地解决。
每个整数一开始都有一个类别，所以我从一组平衡的二叉搜索树（BST）开始。把一个子树从一个BST移动到另一个BST（比如，把一段整数移动到不同的类别）所需的时间相当于合并两个BST，这个过程的时间复杂度是O(n1 * n2)[1]。
这个速度太慢了（在Python中，C语言也不适合），我也没找到利用我数据本身结构来创建一个高效的BST合并操作的方法。
现在我在考虑使用AVL树、红黑树、区间树、二叉堆和treap。比较它们的特性让我感到很困惑。我应该用哪种结构呢？
编辑（问题澄清）：我对如何存储这些值和创建我的数据结构是灵活的，但对输入的接收方式不太灵活，输入来自另一个应用程序，格式如下：CATEGORY(cat3, I, J)。我现在的解决方案是为范围内的每个整数创建一个节点的树。这对于我的数据集大小来说太慢了，所以如果有更好的方法，我很乐意重新设计。
任何请求都可以把任何可能的整数范围移动到任何类别。换句话说，范围是重叠的，比如CATEGORY(cat1, 1, 10)后面跟着CATEGORY(cat3, 5, 15)，但每个整数在任何时候只能属于一个类别。
5 个回答
你可以很简单地在一组连续的整数上建立一个树形结构，这样可以帮助你提高效率。首先，把这个序列重新编号，从0开始，然后找出一个比这个序列范围大的最小的2的幂。
接下来，考虑一下由0到7这几个数字组成的树，这棵树可以用四个数组来表示，每个数组横向排列。
(all)
0-3 4-7
0-1 2-3 4-5 6-7
0 1 2 3 4 5 6 7
给定一个数字和一个层级，我可以通过将这个数字向右移动一定的位数来找到在数组中的偏移量，这个位数是根据层级决定的。
在每个元素中，我可以放一个标记，这个标记可以是“混合”或者是表示该树节点及其下面所有元素的类别。我可以通过从树的根节点一路向下走到叶子节点，来判断一个节点属于哪个类别，直到我看到一个标记不是“混合”的节点为止。我可以在lg n的时间内改变一段数字的类别，因为每一层最多只有两个节点来表示类别：如果有三个节点，其中两个会有相同的父节点，这样我就可以把它们合并。你可能需要稍微调整一下边缘，以确保相邻的范围是正确的，但我认为这个方法在lg n的时间内是可行的。
你可以有一个简单的 Python 字典，格式如下：
1 : { "stop" : 5, "category" : "C1"},
6 : { "stop" : 19, "category" : "C23"},
etc
在这个字典中，键是你范围的起始值，而值则包含这个范围的结束值和它所属的类别。
因为字典的访问速度很快，所以你可以写一些代码，轻松高效地把一个范围移动到另一个类别。最糟糕的情况是，如果你的范围把之前的范围分成了两个或更多部分，你可能需要重新整理一下字典。例如，如果你想把范围 (4, 8) 归入另一个类别，你最终会得到：
1 : { "stop" : 3, "category" : "C1"},
4 : { "stop" : 8, "category" : "new category"},
9 : { "stop" : 19, "category" : "C23"},
etc
找出类别的数量非常简单，只需在常量时间内收集你想要的所有范围，然后统计类别的数量。
编辑：为了成功找到最低（或最高）键以开始进行计算或修改，你还需要一个简单的 Python 列表，里面包含所有排序好的键，以及 bisect 模块。这将帮助你在列表中找到一个位置，以 O(logn) 的时间“放置”范围的起始值，然后除了用 bisect.insort_left 插入新键所需的 O(n) 时间外，其他操作都可以在常量时间内完成。
根据我理解的问题，你有一个范围 [A, B]，并且有以下形式的查询：
- 将特定范围分配给一个类别
E.g. R1 R2 C1 R3 R4 C2
- 查询某个范围内特定类别的总数。例如，查找 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['category'] = set(你在这个类别中拥有的所有范围)
在这种情况下，需要从类别 C1、C2...C4999 中删除之前的范围，以便进行最后的分配（1 5000 C5555）。
或者
1 : { "stop" : 5, "category" : "C1"}, 6 : { "stop" : 19, "category" : "C23"},
在这里，每个起始值（1,2,3,4...,4999）都需要更新类别，以便进行最后的分配（1 5000 C5555）。
一个更好的选择是使用线段树，这样更新范围的复杂度可以降到 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 个字段 [类别, 类别计数[], 需要更新子节点 = false]
1 5 C1
查询会被划分，节点 1:4 的类别会被设置为 C1，且需要更新子节点的标记会被设置为 true，子节点现在不会被更新（记住，只有在需要时才更新，或者使用懒惰传播）。同时节点 5:5 的类别也会被设置为 C1。
3 4 C2
查询会沿着树向 3:4 传播（在这个过程中，为了到达 3:4，1:2 和 3:4 的类别会被更新为 C1，1:4 的需要更新子节点的标记会被设置为 false，1:2 和 3:4 的需要更新子节点的标记会被设置为 true），然后根据当前需求将 3:4 的类别更新为 C2。接下来，它会将 3:4 的需要更新子节点的标记设置为 true，以便将来更新其子节点（在这种情况下已经设置了...没有问题）。