用于存储一长串（大部分是连续的）整数的高效数据结构
Efficient data structure for storing a long sequence of (mostly consecutive) integers
我想要一个数据结构来有效地存储一长串数字。数字应始终为整数，比方说 Longs。
我想利用的输入特征（声称 'efficiency'）是多头将 大部分 连续。可能存在缺失值。并且值可以乱序交互。
我希望数据结构支持以下操作：
- addVal(n): 添加单个值，n
- addRange(n, m): 添加n和m之间的所有值，包括
- delVal(n): 删除单个值，n
- delRange(n, m): 删除n和m之间的所有值，包括
- containsVal(n): return结构中是否存在单个值 n
- containsRange(n, m): return结构中是否存在n和m之间的所有值，incluse
本质上，这是一种更具体的 Set 数据结构，可以利用数据的连续性来使用少于 O(n) 的内存，其中 n 是存储的值的数量。
需要明确的是，虽然我认为此类数据结构的有效实现需要我们在内部存储间隔，但这对用户不可见或不相关。有一些区间树分别存储多个区间，并允许操作找到与给定点或区间重叠的区间数。但从用户的角度来看，这应该完全像一个集合（除了基于范围的操作，因此可以有效地处理批量添加和删除）。
示例：
dataStructure = ...
dataStructure.addRange(1,100) // [(1, 100)]
dataStructure.addRange(200,300) // [(1, 100), (200, 300)]
dataStructure.addVal(199) // [(1, 100), (199, 300)]
dataStructure.delRange(50,250) // [(1, 49), (251, 300)]
我的假设是这最好由一些基于树的结构来实现，但我对如何实现还没有很好的印象。
我想了解是否有一些常用的数据结构已经满足这个用例，因为我不想重新发明轮子。如果没有，我想听听您认为如何最好地实施它。
如果您不关心重复项，那么您的间隔是非重叠的。您需要创建一个保持不变的结构。如果您需要像 numIntervalsContaining(n) 这样的查询，那就是另一个问题了。
您可以使用存储端点对的 BST，就像在 C++ 中一样 std::set<std::pair<long,long>>。解释是每个条目对应区间[n,m]。您需要一个弱排序 - 它是左端点上通常的整数排序。单个 int 或 long n 被插入为 [n,n]。我们必须保持 属性 所有节点间隔都不重叠。下面简单评价一下你的操作顺序。由于您已经指定了 n 我使用 N 作为树的大小。
addVal(n): 添加单个值，n : O(log N)，与 std::set<int> 相同。由于区间不重叠，需要找到n的前导，这可以在O(log n)时间内完成（按照https://www.quora.com/How-can-you-find-successors-and-predecessors-in-a-binary-search-tree-in-order中的案例分解）。查看此前身的右端点，并在必要时扩展区间或添加一个额外的节点 [n,n]，按左端点排序，它始终是右子节点。请注意，如果间隔延长（将 [n+1,n+1] 插入到节点 [a,n] 形成节点 [a,n+1] 的树中），它现在可能会碰到下一个左端点，需要再次合并。所以有一些边缘情况需要考虑。比简单的 BST 稍微复杂一点，但仍然 O(log N)。
addRange(n, m): O(log N)，过程类似。如果插入的区间与另一个区间不平凡地相交，则合并区间以保持非重叠 属性。最坏情况下的性能是 O(n) 如下所述，因为我们插入的子间隔所消耗的子间隔数没有上限。
- delVal(n):
O(log N), 同样是 O(n) 最坏情况，因为我们不知道要删除的区间中包含多少区间。
- delRange(n, m)：删除 n 和 m 之间的所有值，包括：
O(log N)
- containsVal(n)：return结构中是否存在单个值 n：
O(log N)
- containsRange(n, m): return n 和 m 之间的所有值是否存在于结构中：
O(log N)
请注意，我们可以使用正确的 add() 和 addRange() 方法维护非重叠 属性，它已由 delete 方法维护。最坏的情况下我们需要 O(n) 个存储空间。
请注意，所有操作都是 O(log N)，插入范围 [n,m] 与 O(m-n) 或 O(log(m-n)) 或类似的东西完全不同。
我假设您不关心重复项，只关心成员资格。否则你可能需要一个区间树或 KD 树或其他东西，但这些与浮点数据更相关......
间隔树似乎适合存储重叠间隔，而在您的情况下这没有意义。一棵区间树可以容纳数百万个小的重叠区间，它们一起只形成少数较长的非重叠区间。
如果您只想存储非重叠区间，那么添加或删除区间可能涉及删除新区间内的多个连续区间。因此，快速找到连续的间隔并有效删除可能存在的大量间隔非常重要。
这听起来像是不起眼的链表的工作。插入新间隔时，您将：
- 搜索新区间起点的位置。
- 如果在现有区间内，则继续寻找终点位置，同时延长现有区间，删除途中经过的所有区间。
- 如果在现有间隔之间，请检查终点是否在下一个现有间隔之前。如果是，则创建一个新间隔。如果终点出现在下一个现有区间的开始之后，则更改下一个区间的起点，然后按照上一段中的说明继续寻找终点。
删除间隔大致相同：截断起点和终点所在的间隔，并删除其间的所有间隔。
这个的平均和最坏情况下的复杂度是N/2和N，其中N是链表中的区间数。您可以通过添加一种方法来改进这一点，以避免必须遍历整个列表才能找到起点；如果您知道值的范围和分布，这可能类似于散列 table；例如如果值是从 1 到 X 并且分布是均匀的，您将存储一个长度为 Y 的 table，其中每个项目都指向在值 X/Y 之前开始的间隔。添加间隔 (A,B) 时，您将查找 table[A/Y] 并从那里开始迭代链表。 Y 值的选择将取决于您要使用多少 space，以及您希望离起点的实际位置有多近。然后复杂性将下降 Y 倍。
(如果您使用的语言可以缩短链表，并且只留下您切断的对象链进行垃圾收集，您可以找到起点和终点的位置独立的，连接起来，跳过删除中间的所有区间。我不知道这样在实践中是否真的会提高速度。）
这是一个代码示例的开头，包含三个范围函数，但没有进一步优化：
function Interval(a, b, n) {
this.start = a;
this.end = b;
this.next = n;
}
function IntervalList() {
this.first = null;
}
IntervalList.prototype.addRange = function(a, b) {
if (!this.first || b < this.first.start - 1) {
this.first = new Interval(a, b, this.first); // insert as first element
return;
}
var i = this.first;
while (a > i.end + 1 && i.next && b >= i.next.start - 1) {
i = i.next; // locate starting point
}
if (a > i.end + 1) { // insert as new element
i.next = new Interval(a, b, i.next);
return;
}
var j = i.next;
while (j && b >= j.start - 1) { // locate end point
i.end = j.end;
i.next = j = j.next; // discard overlapping interval
}
if (a < i.start) i.start = a; // update interval start
if (b > i.end) i.end = b; // update interval end
}
IntervalList.prototype.delRange = function(a, b) {
if (!this.first || b < this.first.start) return; // range before first interval
var i = this.first;
while (i.next && a > i.next.start) i = i.next; // a in or after interval i
if (a > i.start) { // a in interval
if (b < i.end) { // range in interval -> split
i.next = new Interval(b + 1, i.end, i.next);
i.end = a - 1;
return;
}
if (a <= i.end) i.end = a - 1; // truncate interval
}
var j = a > i.start ? i.next : i;
while (j && b >= j.end) j = j.next; // b before or in interval j
if (a <= this.first.start) this.first = j; // short-circuit list
else i.next = j;
if (j && b >= j.start) j.start = b + 1; // truncate interval
}
IntervalList.prototype.hasRange = function(a, b) {
if (!this.first) return false; // empty list
var i = this.first;
while (i.next && a > i.end) i = i.next; // a before or in interval i
return a >= i.start && b <= i.end; // range in interval ?
}
IntervalList.prototype.addValue = function(a) {
this.addRange(a, a); // could be optimised
}
IntervalList.prototype.delValue = function(a) {
this.delRange(a, a); // could be optimised
}
IntervalList.prototype.hasValue = function(a) {
return this.hasRange(a, a); // could be optimised
}
IntervalList.prototype.print = function() {
var i = this.first;
if (i) do document.write("(" + i.start + "-" + i.end + ") "); while (i = i.next);
document.write("<br>");
}
var intervals = new IntervalList();
intervals.addRange(100,199);
document.write("+ (100-199) → "); intervals.print();
intervals.addRange(300,399);
document.write("+ (300-399) → "); intervals.print();
intervals.addRange(200,299);
document.write("+ (200-299) → "); intervals.print();
intervals.delRange(225,275);
document.write("− (225-275) → "); intervals.print();
document.write("(150-200) ? " + intervals.hasRange(150,200) + "<br>");
document.write("(200-300) ? " + intervals.hasRange(200,300) + "<br>");
另一种选择可能是绳索数据结构 (https://en.m.wikipedia.org/wiki/Rope_(data_structure))，它似乎支持您要求的操作，在 O(log n) 时间内实现。与维基百科中的示例相反，您的示例将存储 [start,end] 而不是字符串子序列。
rope 的有趣之处在于它对区间内索引的高效查找。它通过从左到右对所有值位置进行排序来实现这一点——从低到高的定位（你的间隔将是一个简单的表示）可以是向上或向下，只要移动是向右的——以及依赖存储子树大小，它根据左侧的权重确定当前位置。通过更新和取消链接相关的树段，可以在 O(log n) 时间内用更大的包含间隔吞没部分间隔。
将每个间隔存储为一对（开始，结束）的问题在于，如果您添加一个包含 N 个先前存储的间隔的新 运行ge，则必须销毁这些间隔中的每一个，这需要N步，区间是存储在树、绳还是链表中。
（您可以将它们留给自动垃圾收集，但这也需要时间，并且仅适用于某些语言。）
一个可能的解决方案是将值（不是间隔的起点和终点）存储在 N-ary tree 中，其中每个节点代表一个 运行ge，并存储两个 N -位图，表示 N 个子运行ges 以及这些子运行ges 中的值是否全部存在、全部不存在或混合。在混合的情况下，将有一个指向表示此 rub-运行ge 的子节点的指针。
示例：（使用 branching factor 8 和高度 2 的树）
full range: 0-511 ; store interval 100-300
0-511:
0- 63 64-127 128-191 192-255 256-319 320-383 384-447 448-511
0 mixed 1 1 mixed 0 0 0
64-127:
64- 71 72- 79 80- 87 88- 95 96-103 104-111 112-119 120-127
0 0 0 0 mixed 1 1 1
96-103:
96 97 98 99 100 101 102 103
0 0 0 0 1 1 1 1
256-319:
256-263 264-271 272-279 280-287 288-295 296-303 304-311 312-319
1 1 1 1 1 mixed 0 0
296-303:
296 297 298 299 300 301 302 303
1 1 1 1 1 0 0 0
因此树将包含这五个节点：
- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes
- values: 00000111, mixed: 00001000, 1 pointer to sub-node
- values: 00001111, mixed: 00000000
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
以这种方式存储间隔的要点是您可以丢弃间隔而不必实际删除它。假设您添加了一个新的 运行ge 200-400；在这种情况下，您可以将根节点中的 运行ge 256-319 从 "mixed" 更改为“1”，而不删除或更新 256-319 和 296-303 节点本身；这些节点可以保留以供以后重新使用（或者断开连接并放入可重用子树队列中，或者在程序空闲或 运行 内存不足时在编程的垃圾收集中删除）。
查找区间时，您只需根据需要深入到树中；抬头时，例如225-275，你会发现 192-255 是无所不在的，256-319 是混合的，256-263 和 264-271 和 272-279 是无所不在的，你就会知道答案是正确的。由于这些值将存储为位图（一个用于 present/absent，一个用于 mixed/solid），因此可以仅通过几个按位比较来检查节点中的所有值。
重新使用节点：
如果一个节点有一个子节点，并且相应的值后来从mixed设置为all-absent或all-present，则子节点不再拥有相关值（但它被忽略）。当值改回 mixed 时，可以通过将其所有值设置为其在父节点中的值（在它更改为 mixed 之前）然后进行必要的更改来更新子节点。
在上面的示例中，如果我们添加 运行ge 0-200，这会将树更改为：
- values: 11110000, mixed: 00001000, 2 pointers to sub-nodes
- (values: 00000111, mixed: 00001000, 1 pointer to sub-node)
- (values: 00001111, mixed: 00000000)
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
第二个和第三个节点现在包含过时的值，正在被忽略。如果再删除运行ge 80-95，根节点中运行ge 64-127的值又变成了mixed，运行ge 64-127的节点被重新使用。首先，我们将其中的所有值设置为全部存在（因为那是父节点的先前值），然后我们将 80-87 和 88-95 的值设置为全部不存在。 运行ge 96-103 的第三个节点仍未使用。
- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes
- values: 11001111, mixed: 00000000, 1 pointer to sub-node
- (values: 00001111, mixed: 00000000)
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
如果我们随后添加值 100，则第二个节点中 运行ge 96-103 的值将再次更改为 mixed，第三个节点将更新为 all-absent（其先前的值在第二个节点中）然后值 100 将被设置为呈现：
- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes
- values: 11000111, mixed: 00001000, 1 pointer to sub-node
- values: 00001000, mixed: 00000000
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
乍一看，与将间隔存储为 (start,end) 对的解决方案相比，此数据结构似乎使用了大量存储空间 space。但是，让我们看看（理论上的）最坏情况，在整个 64 位 运行ge 中，每个偶数都存在，每个奇数都不存在：
Total range: 0 ~ 18,446,744,073,709,551,615
Intervals: 9,223,372,036,854,775,808
将这些存储为（开始，结束）对的数据结构将使用：
Nodes: 9,223,372,036,854,775,808
Size of node: 16 bytes
TOTAL: 147,573,952,589,676,412,928 bytes
如果数据结构使用通过（64 位）指针链接的节点，则将添加：
Data: 147,573,952,589,676,412,928 bytes
Pointers: 73,786,976,294,838,206,456 bytes
TOTAL: 221,360,928,884,514,619,384 bytes
具有 b运行ching 因子 64 的 N 叉树（最后一层为 16，得到总 运行ge 为 10×6 + 1×4 = 64 位）将使用：
Nodes (branch): 285,942,833,483,841
Size of branch: 528 bytes
Nodes (leaf): 18,014,398,509,481,984
Size of leaf: 144 bytes
TOTAL: 2,745,051,201,444,873,744 bytes
比 (start,end) 对结构少 53.76 倍（或包括指针在内少 80.64 倍）。
计算是用下面的 N 叉树完成的：
Branch (9 levels):
value: 64-bit map
mixed: 64-bit map
sub-nodes: 64 pointers
TOTAL: 528 bytes
Leaf:
value: 64-bit map
mixed: 64-bit map
sub-nodes: 64 16-bit maps (more efficient than pointing to sub-node)
TOTAL: 144 bytes
这当然是最坏情况下的比较；一般情况在很大程度上取决于具体的输入。
这是我为测试这个想法而编写的第一个代码示例。节点有b运行ching factor 16，这样每层存储4位整数，无需不同的叶子和b运行ches就可以得到共同的位深度。例如，创建深度为 3 的树，表示 4×4 = 16 位的 运行ge。
function setBits(pattern, value, mask) { // helper function (make inline)
return (pattern & ~mask) | (value ? mask : 0);
}
function Node(value) { // CONSTRUCTOR
this.value = value ? 65535 : 0; // set all values to 1 or 0
this.mixed = 0; // set all to non-mixed
this.sub = null; // no pointer array yet
}
Node.prototype.prepareSub = function(pos, mask, value) {
if ((this.mixed & mask) == 0) { // not mixed, child possibly outdated
var prev = (this.value & mask) >> pos;
if (value == prev) return false; // child doesn't require setting
if (!this.sub) this.sub = []; // create array of pointers
if (this.sub[pos]) {
this.sub[pos].value = prev ? 65535 : 0; // update child node values
this.sub[pos].mixed = 0;
}
else this.sub[pos] = new Node(prev); // create new child node
}
return true; // child requires setting
}
Node.prototype.set = function(value, a, b, step) {
var posA = Math.floor(a / step), posB = Math.floor(b / step);
var maskA = 1 << posA, maskB = 1 << posB;
a %= step; b %= step;
if (step == 1) { // node is leaf
var vMask = (maskB | (maskB - 1)) ^ (maskA - 1); // bits posA to posB inclusive
this.value = setBits(this.value, value, vMask);
}
else if (posA == posB) { // only 1 sub-range to be set
if (a == 0 && b == step - 1) // a-b is full sub-range
{
this.value = setBits(this.value, value, maskA);
this.mixed = setBits(this.mixed, 0, maskA);
}
else if (this.prepareSub(posA, maskA, value)) { // child node requires setting
var solid = this.sub[posA].set(value, a, b, step >> 4); // recurse
this.value = setBits(this.value, solid ? value : 0, maskA); // set value
this.mixed = setBits(this.mixed, solid ? 0 : 1, maskA); // set mixed
}
}
else { // multiple sub-ranges to set
var vMask = (maskB - 1) ^ (maskA | (maskA - 1)); // bits between posA and posB
this.value = setBits(this.value, value, vMask); // set inbetween values
this.mixed &= ~vMask; // set inbetween to solid
var solidA = true, solidB = true;
if (a != 0 && this.prepareSub(posA, maskA, value)) { // child needs setting
solidA = this.sub[posA].set(value, a, step - 1, step >> 4);
}
if (b != step - 1 && this.prepareSub(posB, maskB, value)) { // child needs setting
solidB = this.sub[posB].set(value, 0, b, step >> 4);
}
this.value = setBits(this.value, solidA ? value : 0, maskA); // set value
this.value = setBits(this.value, solidB ? value : 0, maskB);
if (solidA) this.mixed &= ~maskA; else this.mixed |= maskA; // set mixed
if (solidB) this.mixed &= ~maskB; else this.mixed |= maskB;
}
return this.mixed == 0 && this.value == 0 || this.value == 65535; // solid or mixed
}
Node.prototype.check = function(a, b, step) {
var posA = Math.floor(a / step), posB = Math.floor(b / step);
var maskA = 1 << posA, maskB = 1 << posB;
a %= step; b %= step;
var vMask = (maskB - 1) ^ (maskA | (maskA - 1)); // bits between posA and posB
if (step == 1) {
vMask = posA == posB ? maskA : vMask | maskA | maskB;
return (this.value & vMask) == vMask;
}
if (posA == posB) {
var present = (this.mixed & maskA) ? this.sub[posA].check(a, b, step >> 4) : this.value & maskA;
return !!present;
}
var present = (this.mixed & maskA) ? this.sub[posA].check(a, step - 1, step >> 4) : this.value & maskA;
if (!present) return false;
present = (this.mixed & maskB) ? this.sub[posB].check(0, b, step >> 4) : this.value & maskB;
if (!present) return false;
return (this.value & vMask) == vMask;
}
function NaryTree(factor, depth) { // CONSTRUCTOR
this.root = new Node();
this.step = Math.pow(factor, depth);
}
NaryTree.prototype.addRange = function(a, b) {
this.root.set(1, a, b, this.step);
}
NaryTree.prototype.delRange = function(a, b) {
this.root.set(0, a, b, this.step);
}
NaryTree.prototype.hasRange = function(a, b) {
return this.root.check(a, b, this.step);
}
var intervals = new NaryTree(16, 3); // create tree for 16-bit range
// CREATE RANDOM DATA AND RUN TEST
document.write("Created N-ary tree for 16-bit range.<br>Randomly adding/deleting 100000 intervals...");
for (var test = 0; test < 100000; test++) {
var a = Math.floor(Math.random() * 61440);
var b = a + Math.floor(Math.random() * 4096);
if (Math.random() > 0.5) intervals.addRange(a,b);
else intervals.delRange(a,b);
}
document.write("<br>Checking a few random intervals:<br>");
for (var test = 0; test < 8; test++) {
var a = Math.floor(Math.random() * 65280);
var b = a + Math.floor(Math.random() * 256);
document.write("Tree has interval " + a + "-" + b + " ? " + intervals.hasRange(a,b),".<br>");
}
我 运行 一个测试来检查正在创建的节点数，以及其中有多少是活动的或休眠的。我总共使用了 24 位的 运行ge（这样我可以在不 运行 内存不足的情况下测试最坏的情况），分为 6 级 4 位（因此每个节点有 16 个子- 运行ges);增加、删除或检查间隔时需要检查或更新的节点数为11或更少。该方案中的最大节点数为 1,118,481。
下图显示了保持 adding/deleting 运行dom 区间为 运行ge 1 (单个整数), 1~16, 1~256 时的活动节点数。 .. 1~16M（满运行ge）。
添加和删除单个整数（深绿色线）创建活动节点，接近最大 1,118,481 个节点，几乎没有节点处于休眠状态。在添加和删除大约 16M 个整数（= 运行ge 中的整数数）后达到最大值。
如果在更大的运行ge中添加和删除运行dom间隔，创建的节点数量大致相同，但更多节点处于休眠状态。如果在完整的1~16M 运行ge（亮黄色线）中添加运行dom间隔，无论你不断添加或删除多少间隔，任何时候都只有不到64个节点处于活动状态。
这已经给出了此数据结构相对于其他数据结构在哪里有用的想法：处于休眠状态的节点越多，在其他方案中需要删除的 intervals/nodes 就越多。
另一方面，它显示了这种数据结构对于某些 运行ges 以及输入的类型和数量来说可能过于 space- 效率低下。您可以引入休眠节点回收系统，但这会剥夺休眠节点可立即重复使用的优势。
N叉树中有很多space被指向子节点的指针占用了。如果完整的 运行ge 足够小，您可以将树存储在数组中。对于 32 位 运行ge，需要 580 MB（"value" 位图需要 546 MB，"mixed" 位图需要 34 MB）。这更 space 高效，因为您只存储位图，并且不需要指向子节点的指针，因为所有内容在数组中都有固定的位置。您将拥有深度为 7 的树的优势，因此任何操作都可以通过检查 15 "nodes" 或更少来完成，并且在 add/delete/check 操作期间不需要创建或删除任何节点。
这是我用来尝试数组中的 N 叉树想法的代码示例；对于 32 位 运行ge（不幸的是，运行ge 超过 40 位左右），它使用 580MB 来存储具有 b运行ching 因子 16 和深度 7 的 N 叉树可能超出任何普通计算机的内存容量）。除了请求的函数之外，它还可以使用 notValue() 和 notRange() 检查间隔是否完全不存在。
#include <iostream>
inline uint16_t setBits(uint16_t pattern, uint16_t mask, uint16_t value) {
return (pattern & ~mask) | (value & mask);
}
class NaryTree32 {
uint16_t value[0x11111111], mixed[0x01111111];
bool set(uint32_t a, uint32_t b, uint16_t value = 0xFFFF, uint8_t bits = 28, uint32_t offset = 0) {
uint8_t posA = a >> bits, posB = b >> bits;
uint16_t maskA = 1 << posA, maskB = 1 << posB;
uint16_t mask = maskB ^ (maskA - 1) ^ (maskB - 1);
// IF NODE IS LEAF: SET VALUE BITS AND RETURN WHETHER VALUES ARE MIXED
if (bits == 0) {
this->value[offset] = setBits(this->value[offset], mask, value);
return this->value[offset] != 0 && this->value[offset] != 0xFFFF;
}
uint32_t offsetA = offset * 16 + posA + 1, offsetB = offset * 16 + posB + 1;
uint32_t subMask = ~(0xFFFFFFFF << bits);
a &= subMask; b &= subMask;
// IF SUB-RANGE A IS MIXED OR HAS WRONG VALUE
if (((this->mixed[offset] & maskA) != 0 || (this->value[offset] & maskA) != (value & maskA))
&& (a != 0 || posA == posB && b != subMask)) {
// IF SUB-RANGE WAS PREVIOUSLY SOLID: UPDATE TO PREVIOUS VALUE
if ((this->mixed[offset] & maskA) == 0) {
this->value[offsetA] = (this->value[offset] & maskA) ? 0xFFFF : 0x0000;
if (bits != 4) this->mixed[offsetA] = 0x0000;
}
// RECURSE AND IF SUB-NODE IS MIXED: SET MIXED BIT AND REMOVE A FROM MASK
if (this->set(a, posA == posB ? b : subMask, value, bits - 4, offsetA)) {
this->mixed[offset] |= maskA;
mask ^= maskA;
}
}
// IF SUB-RANGE B IS MIXED OR HAS WRONG VALUE
if (((this->mixed[offset] & maskB) != 0 || (this->value[offset] & maskB) != (value & maskB))
&& b != subMask && posA != posB) {
// IF SUB-RANGE WAS PREVIOUSLY SOLID: UPDATE SUB-NODE TO PREVIOUS VALUE
if ((this->mixed[offset] & maskB) == 0) {
this->value[offsetB] = (this->value[offset] & maskB) ? 0xFFFF : 0x0000;
if (bits > 4) this->mixed[offsetB] = 0x0000;
}
// RECURSE AND IF SUB-NODE IS MIXED: SET MIXED BIT AND REMOVE A FROM MASK
if (this->set(0, b, value, bits - 4, offsetB)) {
this->mixed[offset] |= maskB;
mask ^= maskB;
}
}
// SET VALUE AND MIXED BITS THAT HAVEN'T BEEN SET YET AND RETURN WHETHER NODE IS MIXED
if (mask) {
this->value[offset] = setBits(this->value[offset], mask, value);
this->mixed[offset] &= ~mask;
}
return this->mixed[offset] != 0 || this->value[offset] != 0 && this->value[offset] != 0xFFFF;
}
bool check(uint32_t a, uint32_t b, uint16_t value = 0xFFFF, uint8_t bits = 28, uint32_t offset = 0) {
uint8_t posA = a >> bits, posB = b >> bits;
uint16_t maskA = 1 << posA, maskB = 1 << posB;
uint16_t mask = maskB ^ (maskA - 1) ^ (maskB - 1);
// IF NODE IS LEAF: CHECK BITS A TO B INCLUSIVE AND RETURN
if (bits == 0) {
return (this->value[offset] & mask) == (value & mask);
}
uint32_t subMask = ~(0xFFFFFFFF << bits);
a &= subMask; b &= subMask;
// IF SUB-RANGE A IS MIXED AND PART OF IT NEEDS CHECKING: RECURSE AND RETURN IF FALSE
if ((this->mixed[offset] & maskA) && (a != 0 || posA == posB && b != subMask)) {
if (this->check(a, posA == posB ? b : subMask, value, bits - 4, offset * 16 + posA + 1)) {
mask ^= maskA;
}
else return false;
}
// IF SUB-RANGE B IS MIXED AND PART OF IT NEEDS CHECKING: RECURSE AND RETURN IF FALSE
if (posA != posB && (this->mixed[offset] & maskB) && b != subMask) {
if (this->check(0, b, value, bits - 4, offset * 16 + posB + 1)) {
mask ^= maskB;
}
else return false;
}
// CHECK INBETWEEN BITS (AND A AND/OR B IF NOT YET CHECKED) WHETHER SOLID AND CORRECT
return (this->mixed[offset] & mask) == 0 && (this->value[offset] & mask) == (value & mask);
}
public:
NaryTree32() { // CONSTRUCTOR: INITIALISES ROOT NODE
this->value[0] = 0x0000;
this->mixed[0] = 0x0000;
}
void addValue(uint32_t a) {this->set(a, a);}
void addRange(uint32_t a, uint32_t b) {this->set(a, b);}
void delValue(uint32_t a) {this->set(a, a, 0);}
void delRange(uint32_t a, uint32_t b) {this->set(a, b, 0);}
bool hasValue(uint32_t a) {return this->check(a, a);}
bool hasRange(uint32_t a, uint32_t b) {return this->check(a, b);}
bool notValue(uint32_t a) {return this->check(a, a, 0);}
bool notRange(uint32_t a, uint32_t b) {return this->check(a, b, 0);}
};
int main() {
NaryTree32 *tree = new NaryTree32();
tree->addRange(4294967280, 4294967295);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
tree->delValue(4294967290);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
tree->addRange(1000000000, 4294967295);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
tree->delRange(2000000000, 4294967280);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
return 0;
}
我很惊讶没有人建议 segment trees 存储值的整数域。 （当用于 2d 和 3d 图形等几何应用程序时，它们分别称为四叉树和八叉树。）插入、删除和查找的时间和 space 复杂度与 (maxval - minval) 中的位数成正比)，即log_2(maxval - minval)，整数数据域的最大值和最小值。
简而言之，我们在 [minval, maxval] 中编码一组整数。最顶层 0 的节点代表整个范围。每个连续级别的节点代表 sub-ranges 的近似大小 (maxval - minval) / 2^k。当包含一个节点时，它对应值的某些子集是表示集的一部分。当它是一片叶子时，它的 all 个值都在集合中。当它不存在时，none 是。
例如如果minval=0且maxval=7，则k=0节点的k=1children表示[0..3]和[4..7]。它们在k=2层的children是[0..1][2..3][4..5]和[6..7]，k=3个节点代表单个元素。集合 {[1..3], [6..7]} 将是树（从左到右的级别）：
[0..7] -- [0..3] -- [0..1]
| | `-[1]
| `- [2..3]
` [4..7]
`- [6..7]
不难看出树的 space 将是 O(m log (maxval - minval))，其中 m 是存储在树中的间隔数。
使用带动态插入和删除的线段树并不常见，但事实证明算法相当简单。需要注意确保节点数量最少。
这里是一些经过简单测试的 java 代码。
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class SegmentTree {
// Shouldn't differ by more than Long.MAX_VALUE to prevent overflow.
static final long MIN_VAL = 0;
static final long MAX_VAL = Long.MAX_VALUE;
Node root;
static class Node {
Node left;
Node right;
Node(Node left, Node right) {
this.left = left;
this.right = right;
}
}
private static boolean isLeaf(Node node) {
return node != null && node.left == null && node.right == null;
}
private static Node reset(Node node, Node left, Node right) {
if (node == null) {
return new Node(left, right);
}
node.left = left;
node.right = right;
return node;
}
/**
* Accept an arbitrary subtree rooted at a node representing a subset S of the range [lo,hi] and
* transform it into a subtree representing S + [a,b]. It's assumed a >= lo and b <= hi.
*/
private static Node add(Node node, long lo, long hi, long a, long b) {
// If the range is empty, the interval tree is always null.
if (lo > hi) return null;
// If this is a leaf or insertion is outside the range, there's no change.
if (isLeaf(node) || a > b || b < lo || a > hi) return node;
// If insertion fills the range, return a leaf.
if (a == lo && b == hi) return reset(node, null, null);
// Insertion doesn't cover the range. Get the children, if any.
Node left = null, right = null;
if (node != null) {
left = node.left;
right = node.right;
}
// Split the range and recur to insert in halves.
long mid = lo + (hi - lo) / 2;
left = add(left, lo, mid, a, Math.min(b, mid));
right = add(right, mid + 1, hi, Math.max(a, mid + 1), b);
// Build a new node, coallescing to leaf if both children are leaves.
return isLeaf(left) && isLeaf(right) ? reset(node, null, null) : reset(node, left, right);
}
/**
* Accept an arbitrary subtree rooted at a node representing a subset S of the range [lo,hi] and
* transform it into a subtree representing range(s) S - [a,b]. It's assumed a >= lo and b <= hi.
*/
private static Node del(Node node, long lo, long hi, long a, long b) {
// If the tree is null, we can't remove anything, so it's still null
// or if the range is empty, the tree is null.
if (node == null || lo > hi) return null;
// If the deletion is outside the range, there's no change.
if (a > b || b < lo || a > hi) return node;
// If deletion fills the range, return an empty tree.
if (a == lo && b == hi) return null;
// Deletion doesn't fill the range.
// Replace a leaf with a tree that has the deleted portion removed.
if (isLeaf(node)) {
return add(add(null, lo, hi, b + 1, hi), lo, hi, lo, a - 1);
}
// Not a leaf. Get children, if any.
Node left = node.left, right = node.right;
long mid = lo + (hi - lo) / 2;
// Recur to delete in child ranges.
left = del(left, lo, mid, a, Math.min(b, mid));
right = del(right, mid + 1, hi, Math.max(a, mid + 1), b);
// Build a new node, coallescing to empty tree if both children are empty.
return left == null && right == null ? null : reset(node, left, right);
}
private static class NotContainedException extends Exception {};
private static void verifyContains(Node node, long lo, long hi, long a, long b)
throws NotContainedException {
// If this is a leaf or query is empty, it's always contained.
if (isLeaf(node) || a > b) return;
// If tree or search range is empty, the query is never contained.
if (node == null || lo > hi) throw new NotContainedException();
long mid = lo + (hi - lo) / 2;
verifyContains(node.left, lo, mid, a, Math.min(b, mid));
verifyContains(node.right, mid + 1, hi, Math.max(a, mid + 1), b);
}
SegmentTree addRange(long a, long b) {
root = add(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
return this;
}
SegmentTree addVal(long a) {
return addRange(a, a);
}
SegmentTree delRange(long a, long b) {
root = del(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
return this;
}
SegmentTree delVal(long a) {
return delRange(a, a);
}
boolean containsVal(long a) {
return containsRange(a, a);
}
boolean containsRange(long a, long b) {
try {
verifyContains(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
return true;
} catch (NotContainedException expected) {
return false;
}
}
private static final boolean PRINT_SEGS_COALESCED = true;
/** Gather a list of possibly coalesced segments for printing. */
private static void gatherSegs(List<Long> segs, Node node, long lo, long hi) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
if (PRINT_SEGS_COALESCED && !segs.isEmpty() && segs.get(segs.size() - 1) == lo - 1) {
segs.remove(segs.size() - 1);
} else {
segs.add(lo);
}
segs.add(hi);
} else {
long mid = lo + (hi - lo) / 2;
gatherSegs(segs, node.left, lo, mid);
gatherSegs(segs, node.right, mid + 1, hi);
}
}
SegmentTree print() {
List<Long> segs = new ArrayList<>();
gatherSegs(segs, root, MIN_VAL, MAX_VAL);
Iterator<Long> it = segs.iterator();
while (it.hasNext()) {
long a = it.next();
long b = it.next();
System.out.print("[" + a + "," + b + "]");
}
System.out.println();
return this;
}
public static void main(String [] args) {
SegmentTree tree = new SegmentTree()
.addRange(0, 4).print()
.addRange(6, 7).print()
.delVal(2).print()
.addVal(5).print()
.addRange(0,1000).print()
.addVal(5).print()
.delRange(22, 777).print();
System.out.println(tree.containsRange(3, 20));
}
}
我想要一个数据结构来有效地存储一长串数字。数字应始终为整数，比方说 Longs。
我想利用的输入特征（声称 'efficiency'）是多头将 大部分 连续。可能存在缺失值。并且值可以乱序交互。
我希望数据结构支持以下操作：
- addVal(n): 添加单个值，n
- addRange(n, m): 添加n和m之间的所有值，包括
- delVal(n): 删除单个值，n
- delRange(n, m): 删除n和m之间的所有值，包括
- containsVal(n): return结构中是否存在单个值 n
- containsRange(n, m): return结构中是否存在n和m之间的所有值，incluse
本质上，这是一种更具体的 Set 数据结构，可以利用数据的连续性来使用少于 O(n) 的内存，其中 n 是存储的值的数量。
需要明确的是，虽然我认为此类数据结构的有效实现需要我们在内部存储间隔，但这对用户不可见或不相关。有一些区间树分别存储多个区间，并允许操作找到与给定点或区间重叠的区间数。但从用户的角度来看，这应该完全像一个集合（除了基于范围的操作，因此可以有效地处理批量添加和删除）。
示例：
dataStructure = ...
dataStructure.addRange(1,100) // [(1, 100)]
dataStructure.addRange(200,300) // [(1, 100), (200, 300)]
dataStructure.addVal(199) // [(1, 100), (199, 300)]
dataStructure.delRange(50,250) // [(1, 49), (251, 300)]
我的假设是这最好由一些基于树的结构来实现，但我对如何实现还没有很好的印象。 我想了解是否有一些常用的数据结构已经满足这个用例，因为我不想重新发明轮子。如果没有，我想听听您认为如何最好地实施它。
如果您不关心重复项，那么您的间隔是非重叠的。您需要创建一个保持不变的结构。如果您需要像 numIntervalsContaining(n) 这样的查询，那就是另一个问题了。
您可以使用存储端点对的 BST，就像在 C++ 中一样 std::set<std::pair<long,long>>。解释是每个条目对应区间[n,m]。您需要一个弱排序 - 它是左端点上通常的整数排序。单个 int 或 long n 被插入为 [n,n]。我们必须保持 属性 所有节点间隔都不重叠。下面简单评价一下你的操作顺序。由于您已经指定了 n 我使用 N 作为树的大小。
addVal(n): 添加单个值，n :
O(log N)，与std::set<int>相同。由于区间不重叠，需要找到n的前导，这可以在O(log n)时间内完成（按照https://www.quora.com/How-can-you-find-successors-and-predecessors-in-a-binary-search-tree-in-order中的案例分解）。查看此前身的右端点，并在必要时扩展区间或添加一个额外的节点[n,n]，按左端点排序，它始终是右子节点。请注意，如果间隔延长（将[n+1,n+1]插入到节点[a,n]形成节点[a,n+1]的树中），它现在可能会碰到下一个左端点，需要再次合并。所以有一些边缘情况需要考虑。比简单的 BST 稍微复杂一点，但仍然O(log N)。addRange(n, m):
O(log N)，过程类似。如果插入的区间与另一个区间不平凡地相交，则合并区间以保持非重叠 属性。最坏情况下的性能是O(n)如下所述，因为我们插入的子间隔所消耗的子间隔数没有上限。- delVal(n):
O(log N), 同样是O(n)最坏情况，因为我们不知道要删除的区间中包含多少区间。 - delRange(n, m)：删除 n 和 m 之间的所有值，包括：
O(log N) - containsVal(n)：return结构中是否存在单个值 n：
O(log N) - containsRange(n, m): return n 和 m 之间的所有值是否存在于结构中：
O(log N)
请注意，我们可以使用正确的 add() 和 addRange() 方法维护非重叠 属性，它已由 delete 方法维护。最坏的情况下我们需要 O(n) 个存储空间。
请注意，所有操作都是 O(log N)，插入范围 [n,m] 与 O(m-n) 或 O(log(m-n)) 或类似的东西完全不同。
我假设您不关心重复项，只关心成员资格。否则你可能需要一个区间树或 KD 树或其他东西，但这些与浮点数据更相关......
间隔树似乎适合存储重叠间隔，而在您的情况下这没有意义。一棵区间树可以容纳数百万个小的重叠区间，它们一起只形成少数较长的非重叠区间。
如果您只想存储非重叠区间，那么添加或删除区间可能涉及删除新区间内的多个连续区间。因此，快速找到连续的间隔并有效删除可能存在的大量间隔非常重要。
这听起来像是不起眼的链表的工作。插入新间隔时，您将：
- 搜索新区间起点的位置。
- 如果在现有区间内，则继续寻找终点位置，同时延长现有区间，删除途中经过的所有区间。
- 如果在现有间隔之间，请检查终点是否在下一个现有间隔之前。如果是，则创建一个新间隔。如果终点出现在下一个现有区间的开始之后，则更改下一个区间的起点，然后按照上一段中的说明继续寻找终点。
删除间隔大致相同：截断起点和终点所在的间隔，并删除其间的所有间隔。
这个的平均和最坏情况下的复杂度是N/2和N，其中N是链表中的区间数。您可以通过添加一种方法来改进这一点，以避免必须遍历整个列表才能找到起点；如果您知道值的范围和分布，这可能类似于散列 table；例如如果值是从 1 到 X 并且分布是均匀的，您将存储一个长度为 Y 的 table，其中每个项目都指向在值 X/Y 之前开始的间隔。添加间隔 (A,B) 时，您将查找 table[A/Y] 并从那里开始迭代链表。 Y 值的选择将取决于您要使用多少 space，以及您希望离起点的实际位置有多近。然后复杂性将下降 Y 倍。
(如果您使用的语言可以缩短链表，并且只留下您切断的对象链进行垃圾收集，您可以找到起点和终点的位置独立的，连接起来，跳过删除中间的所有区间。我不知道这样在实践中是否真的会提高速度。）
这是一个代码示例的开头，包含三个范围函数，但没有进一步优化：
function Interval(a, b, n) {
this.start = a;
this.end = b;
this.next = n;
}
function IntervalList() {
this.first = null;
}
IntervalList.prototype.addRange = function(a, b) {
if (!this.first || b < this.first.start - 1) {
this.first = new Interval(a, b, this.first); // insert as first element
return;
}
var i = this.first;
while (a > i.end + 1 && i.next && b >= i.next.start - 1) {
i = i.next; // locate starting point
}
if (a > i.end + 1) { // insert as new element
i.next = new Interval(a, b, i.next);
return;
}
var j = i.next;
while (j && b >= j.start - 1) { // locate end point
i.end = j.end;
i.next = j = j.next; // discard overlapping interval
}
if (a < i.start) i.start = a; // update interval start
if (b > i.end) i.end = b; // update interval end
}
IntervalList.prototype.delRange = function(a, b) {
if (!this.first || b < this.first.start) return; // range before first interval
var i = this.first;
while (i.next && a > i.next.start) i = i.next; // a in or after interval i
if (a > i.start) { // a in interval
if (b < i.end) { // range in interval -> split
i.next = new Interval(b + 1, i.end, i.next);
i.end = a - 1;
return;
}
if (a <= i.end) i.end = a - 1; // truncate interval
}
var j = a > i.start ? i.next : i;
while (j && b >= j.end) j = j.next; // b before or in interval j
if (a <= this.first.start) this.first = j; // short-circuit list
else i.next = j;
if (j && b >= j.start) j.start = b + 1; // truncate interval
}
IntervalList.prototype.hasRange = function(a, b) {
if (!this.first) return false; // empty list
var i = this.first;
while (i.next && a > i.end) i = i.next; // a before or in interval i
return a >= i.start && b <= i.end; // range in interval ?
}
IntervalList.prototype.addValue = function(a) {
this.addRange(a, a); // could be optimised
}
IntervalList.prototype.delValue = function(a) {
this.delRange(a, a); // could be optimised
}
IntervalList.prototype.hasValue = function(a) {
return this.hasRange(a, a); // could be optimised
}
IntervalList.prototype.print = function() {
var i = this.first;
if (i) do document.write("(" + i.start + "-" + i.end + ") "); while (i = i.next);
document.write("<br>");
}
var intervals = new IntervalList();
intervals.addRange(100,199);
document.write("+ (100-199) → "); intervals.print();
intervals.addRange(300,399);
document.write("+ (300-399) → "); intervals.print();
intervals.addRange(200,299);
document.write("+ (200-299) → "); intervals.print();
intervals.delRange(225,275);
document.write("− (225-275) → "); intervals.print();
document.write("(150-200) ? " + intervals.hasRange(150,200) + "<br>");
document.write("(200-300) ? " + intervals.hasRange(200,300) + "<br>");
另一种选择可能是绳索数据结构 (https://en.m.wikipedia.org/wiki/Rope_(data_structure))，它似乎支持您要求的操作，在 O(log n) 时间内实现。与维基百科中的示例相反，您的示例将存储 [start,end] 而不是字符串子序列。
rope 的有趣之处在于它对区间内索引的高效查找。它通过从左到右对所有值位置进行排序来实现这一点——从低到高的定位（你的间隔将是一个简单的表示）可以是向上或向下，只要移动是向右的——以及依赖存储子树大小，它根据左侧的权重确定当前位置。通过更新和取消链接相关的树段，可以在 O(log n) 时间内用更大的包含间隔吞没部分间隔。
将每个间隔存储为一对（开始，结束）的问题在于，如果您添加一个包含 N 个先前存储的间隔的新 运行ge，则必须销毁这些间隔中的每一个，这需要N步，区间是存储在树、绳还是链表中。
（您可以将它们留给自动垃圾收集，但这也需要时间，并且仅适用于某些语言。）
一个可能的解决方案是将值（不是间隔的起点和终点）存储在 N-ary tree 中，其中每个节点代表一个 运行ge，并存储两个 N -位图，表示 N 个子运行ges 以及这些子运行ges 中的值是否全部存在、全部不存在或混合。在混合的情况下，将有一个指向表示此 rub-运行ge 的子节点的指针。
示例：（使用 branching factor 8 和高度 2 的树）
full range: 0-511 ; store interval 100-300
0-511:
0- 63 64-127 128-191 192-255 256-319 320-383 384-447 448-511
0 mixed 1 1 mixed 0 0 0
64-127:
64- 71 72- 79 80- 87 88- 95 96-103 104-111 112-119 120-127
0 0 0 0 mixed 1 1 1
96-103:
96 97 98 99 100 101 102 103
0 0 0 0 1 1 1 1
256-319:
256-263 264-271 272-279 280-287 288-295 296-303 304-311 312-319
1 1 1 1 1 mixed 0 0
296-303:
296 297 298 299 300 301 302 303
1 1 1 1 1 0 0 0
因此树将包含这五个节点：
- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes
- values: 00000111, mixed: 00001000, 1 pointer to sub-node
- values: 00001111, mixed: 00000000
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
以这种方式存储间隔的要点是您可以丢弃间隔而不必实际删除它。假设您添加了一个新的 运行ge 200-400；在这种情况下，您可以将根节点中的 运行ge 256-319 从 "mixed" 更改为“1”，而不删除或更新 256-319 和 296-303 节点本身；这些节点可以保留以供以后重新使用（或者断开连接并放入可重用子树队列中，或者在程序空闲或 运行 内存不足时在编程的垃圾收集中删除）。
查找区间时，您只需根据需要深入到树中；抬头时，例如225-275，你会发现 192-255 是无所不在的，256-319 是混合的，256-263 和 264-271 和 272-279 是无所不在的，你就会知道答案是正确的。由于这些值将存储为位图（一个用于 present/absent，一个用于 mixed/solid），因此可以仅通过几个按位比较来检查节点中的所有值。
重新使用节点：
如果一个节点有一个子节点，并且相应的值后来从mixed设置为all-absent或all-present，则子节点不再拥有相关值（但它被忽略）。当值改回 mixed 时，可以通过将其所有值设置为其在父节点中的值（在它更改为 mixed 之前）然后进行必要的更改来更新子节点。
在上面的示例中，如果我们添加 运行ge 0-200，这会将树更改为：
- values: 11110000, mixed: 00001000, 2 pointers to sub-nodes
- (values: 00000111, mixed: 00001000, 1 pointer to sub-node)
- (values: 00001111, mixed: 00000000)
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
第二个和第三个节点现在包含过时的值，正在被忽略。如果再删除运行ge 80-95，根节点中运行ge 64-127的值又变成了mixed，运行ge 64-127的节点被重新使用。首先，我们将其中的所有值设置为全部存在（因为那是父节点的先前值），然后我们将 80-87 和 88-95 的值设置为全部不存在。 运行ge 96-103 的第三个节点仍未使用。
- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes
- values: 11001111, mixed: 00000000, 1 pointer to sub-node
- (values: 00001111, mixed: 00000000)
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
如果我们随后添加值 100，则第二个节点中 运行ge 96-103 的值将再次更改为 mixed，第三个节点将更新为 all-absent（其先前的值在第二个节点中）然后值 100 将被设置为呈现：
- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes
- values: 11000111, mixed: 00001000, 1 pointer to sub-node
- values: 00001000, mixed: 00000000
- values: 11111000, mixed: 00000100, 1 pointer to sub-node
- values: 11111000, mixed: 00000000
乍一看，与将间隔存储为 (start,end) 对的解决方案相比，此数据结构似乎使用了大量存储空间 space。但是，让我们看看（理论上的）最坏情况，在整个 64 位 运行ge 中，每个偶数都存在，每个奇数都不存在：
Total range: 0 ~ 18,446,744,073,709,551,615
Intervals: 9,223,372,036,854,775,808
将这些存储为（开始，结束）对的数据结构将使用：
Nodes: 9,223,372,036,854,775,808
Size of node: 16 bytes
TOTAL: 147,573,952,589,676,412,928 bytes
如果数据结构使用通过（64 位）指针链接的节点，则将添加：
Data: 147,573,952,589,676,412,928 bytes
Pointers: 73,786,976,294,838,206,456 bytes
TOTAL: 221,360,928,884,514,619,384 bytes
具有 b运行ching 因子 64 的 N 叉树（最后一层为 16，得到总 运行ge 为 10×6 + 1×4 = 64 位）将使用：
Nodes (branch): 285,942,833,483,841
Size of branch: 528 bytes
Nodes (leaf): 18,014,398,509,481,984
Size of leaf: 144 bytes
TOTAL: 2,745,051,201,444,873,744 bytes
比 (start,end) 对结构少 53.76 倍（或包括指针在内少 80.64 倍）。
计算是用下面的 N 叉树完成的：
Branch (9 levels):
value: 64-bit map
mixed: 64-bit map
sub-nodes: 64 pointers
TOTAL: 528 bytes
Leaf:
value: 64-bit map
mixed: 64-bit map
sub-nodes: 64 16-bit maps (more efficient than pointing to sub-node)
TOTAL: 144 bytes
这当然是最坏情况下的比较；一般情况在很大程度上取决于具体的输入。
这是我为测试这个想法而编写的第一个代码示例。节点有b运行ching factor 16，这样每层存储4位整数，无需不同的叶子和b运行ches就可以得到共同的位深度。例如，创建深度为 3 的树，表示 4×4 = 16 位的 运行ge。
function setBits(pattern, value, mask) { // helper function (make inline)
return (pattern & ~mask) | (value ? mask : 0);
}
function Node(value) { // CONSTRUCTOR
this.value = value ? 65535 : 0; // set all values to 1 or 0
this.mixed = 0; // set all to non-mixed
this.sub = null; // no pointer array yet
}
Node.prototype.prepareSub = function(pos, mask, value) {
if ((this.mixed & mask) == 0) { // not mixed, child possibly outdated
var prev = (this.value & mask) >> pos;
if (value == prev) return false; // child doesn't require setting
if (!this.sub) this.sub = []; // create array of pointers
if (this.sub[pos]) {
this.sub[pos].value = prev ? 65535 : 0; // update child node values
this.sub[pos].mixed = 0;
}
else this.sub[pos] = new Node(prev); // create new child node
}
return true; // child requires setting
}
Node.prototype.set = function(value, a, b, step) {
var posA = Math.floor(a / step), posB = Math.floor(b / step);
var maskA = 1 << posA, maskB = 1 << posB;
a %= step; b %= step;
if (step == 1) { // node is leaf
var vMask = (maskB | (maskB - 1)) ^ (maskA - 1); // bits posA to posB inclusive
this.value = setBits(this.value, value, vMask);
}
else if (posA == posB) { // only 1 sub-range to be set
if (a == 0 && b == step - 1) // a-b is full sub-range
{
this.value = setBits(this.value, value, maskA);
this.mixed = setBits(this.mixed, 0, maskA);
}
else if (this.prepareSub(posA, maskA, value)) { // child node requires setting
var solid = this.sub[posA].set(value, a, b, step >> 4); // recurse
this.value = setBits(this.value, solid ? value : 0, maskA); // set value
this.mixed = setBits(this.mixed, solid ? 0 : 1, maskA); // set mixed
}
}
else { // multiple sub-ranges to set
var vMask = (maskB - 1) ^ (maskA | (maskA - 1)); // bits between posA and posB
this.value = setBits(this.value, value, vMask); // set inbetween values
this.mixed &= ~vMask; // set inbetween to solid
var solidA = true, solidB = true;
if (a != 0 && this.prepareSub(posA, maskA, value)) { // child needs setting
solidA = this.sub[posA].set(value, a, step - 1, step >> 4);
}
if (b != step - 1 && this.prepareSub(posB, maskB, value)) { // child needs setting
solidB = this.sub[posB].set(value, 0, b, step >> 4);
}
this.value = setBits(this.value, solidA ? value : 0, maskA); // set value
this.value = setBits(this.value, solidB ? value : 0, maskB);
if (solidA) this.mixed &= ~maskA; else this.mixed |= maskA; // set mixed
if (solidB) this.mixed &= ~maskB; else this.mixed |= maskB;
}
return this.mixed == 0 && this.value == 0 || this.value == 65535; // solid or mixed
}
Node.prototype.check = function(a, b, step) {
var posA = Math.floor(a / step), posB = Math.floor(b / step);
var maskA = 1 << posA, maskB = 1 << posB;
a %= step; b %= step;
var vMask = (maskB - 1) ^ (maskA | (maskA - 1)); // bits between posA and posB
if (step == 1) {
vMask = posA == posB ? maskA : vMask | maskA | maskB;
return (this.value & vMask) == vMask;
}
if (posA == posB) {
var present = (this.mixed & maskA) ? this.sub[posA].check(a, b, step >> 4) : this.value & maskA;
return !!present;
}
var present = (this.mixed & maskA) ? this.sub[posA].check(a, step - 1, step >> 4) : this.value & maskA;
if (!present) return false;
present = (this.mixed & maskB) ? this.sub[posB].check(0, b, step >> 4) : this.value & maskB;
if (!present) return false;
return (this.value & vMask) == vMask;
}
function NaryTree(factor, depth) { // CONSTRUCTOR
this.root = new Node();
this.step = Math.pow(factor, depth);
}
NaryTree.prototype.addRange = function(a, b) {
this.root.set(1, a, b, this.step);
}
NaryTree.prototype.delRange = function(a, b) {
this.root.set(0, a, b, this.step);
}
NaryTree.prototype.hasRange = function(a, b) {
return this.root.check(a, b, this.step);
}
var intervals = new NaryTree(16, 3); // create tree for 16-bit range
// CREATE RANDOM DATA AND RUN TEST
document.write("Created N-ary tree for 16-bit range.<br>Randomly adding/deleting 100000 intervals...");
for (var test = 0; test < 100000; test++) {
var a = Math.floor(Math.random() * 61440);
var b = a + Math.floor(Math.random() * 4096);
if (Math.random() > 0.5) intervals.addRange(a,b);
else intervals.delRange(a,b);
}
document.write("<br>Checking a few random intervals:<br>");
for (var test = 0; test < 8; test++) {
var a = Math.floor(Math.random() * 65280);
var b = a + Math.floor(Math.random() * 256);
document.write("Tree has interval " + a + "-" + b + " ? " + intervals.hasRange(a,b),".<br>");
}
我 运行 一个测试来检查正在创建的节点数，以及其中有多少是活动的或休眠的。我总共使用了 24 位的 运行ge（这样我可以在不 运行 内存不足的情况下测试最坏的情况），分为 6 级 4 位（因此每个节点有 16 个子- 运行ges);增加、删除或检查间隔时需要检查或更新的节点数为11或更少。该方案中的最大节点数为 1,118,481。
下图显示了保持 adding/deleting 运行dom 区间为 运行ge 1 (单个整数), 1~16, 1~256 时的活动节点数。 .. 1~16M（满运行ge）。
添加和删除单个整数（深绿色线）创建活动节点，接近最大 1,118,481 个节点，几乎没有节点处于休眠状态。在添加和删除大约 16M 个整数（= 运行ge 中的整数数）后达到最大值。
如果在更大的运行ge中添加和删除运行dom间隔，创建的节点数量大致相同，但更多节点处于休眠状态。如果在完整的1~16M 运行ge（亮黄色线）中添加运行dom间隔，无论你不断添加或删除多少间隔，任何时候都只有不到64个节点处于活动状态。
这已经给出了此数据结构相对于其他数据结构在哪里有用的想法：处于休眠状态的节点越多，在其他方案中需要删除的 intervals/nodes 就越多。
另一方面，它显示了这种数据结构对于某些 运行ges 以及输入的类型和数量来说可能过于 space- 效率低下。您可以引入休眠节点回收系统，但这会剥夺休眠节点可立即重复使用的优势。
N叉树中有很多space被指向子节点的指针占用了。如果完整的 运行ge 足够小，您可以将树存储在数组中。对于 32 位 运行ge，需要 580 MB（"value" 位图需要 546 MB，"mixed" 位图需要 34 MB）。这更 space 高效，因为您只存储位图，并且不需要指向子节点的指针，因为所有内容在数组中都有固定的位置。您将拥有深度为 7 的树的优势，因此任何操作都可以通过检查 15 "nodes" 或更少来完成，并且在 add/delete/check 操作期间不需要创建或删除任何节点。
这是我用来尝试数组中的 N 叉树想法的代码示例；对于 32 位 运行ge（不幸的是，运行ge 超过 40 位左右），它使用 580MB 来存储具有 b运行ching 因子 16 和深度 7 的 N 叉树可能超出任何普通计算机的内存容量）。除了请求的函数之外，它还可以使用 notValue() 和 notRange() 检查间隔是否完全不存在。
#include <iostream>
inline uint16_t setBits(uint16_t pattern, uint16_t mask, uint16_t value) {
return (pattern & ~mask) | (value & mask);
}
class NaryTree32 {
uint16_t value[0x11111111], mixed[0x01111111];
bool set(uint32_t a, uint32_t b, uint16_t value = 0xFFFF, uint8_t bits = 28, uint32_t offset = 0) {
uint8_t posA = a >> bits, posB = b >> bits;
uint16_t maskA = 1 << posA, maskB = 1 << posB;
uint16_t mask = maskB ^ (maskA - 1) ^ (maskB - 1);
// IF NODE IS LEAF: SET VALUE BITS AND RETURN WHETHER VALUES ARE MIXED
if (bits == 0) {
this->value[offset] = setBits(this->value[offset], mask, value);
return this->value[offset] != 0 && this->value[offset] != 0xFFFF;
}
uint32_t offsetA = offset * 16 + posA + 1, offsetB = offset * 16 + posB + 1;
uint32_t subMask = ~(0xFFFFFFFF << bits);
a &= subMask; b &= subMask;
// IF SUB-RANGE A IS MIXED OR HAS WRONG VALUE
if (((this->mixed[offset] & maskA) != 0 || (this->value[offset] & maskA) != (value & maskA))
&& (a != 0 || posA == posB && b != subMask)) {
// IF SUB-RANGE WAS PREVIOUSLY SOLID: UPDATE TO PREVIOUS VALUE
if ((this->mixed[offset] & maskA) == 0) {
this->value[offsetA] = (this->value[offset] & maskA) ? 0xFFFF : 0x0000;
if (bits != 4) this->mixed[offsetA] = 0x0000;
}
// RECURSE AND IF SUB-NODE IS MIXED: SET MIXED BIT AND REMOVE A FROM MASK
if (this->set(a, posA == posB ? b : subMask, value, bits - 4, offsetA)) {
this->mixed[offset] |= maskA;
mask ^= maskA;
}
}
// IF SUB-RANGE B IS MIXED OR HAS WRONG VALUE
if (((this->mixed[offset] & maskB) != 0 || (this->value[offset] & maskB) != (value & maskB))
&& b != subMask && posA != posB) {
// IF SUB-RANGE WAS PREVIOUSLY SOLID: UPDATE SUB-NODE TO PREVIOUS VALUE
if ((this->mixed[offset] & maskB) == 0) {
this->value[offsetB] = (this->value[offset] & maskB) ? 0xFFFF : 0x0000;
if (bits > 4) this->mixed[offsetB] = 0x0000;
}
// RECURSE AND IF SUB-NODE IS MIXED: SET MIXED BIT AND REMOVE A FROM MASK
if (this->set(0, b, value, bits - 4, offsetB)) {
this->mixed[offset] |= maskB;
mask ^= maskB;
}
}
// SET VALUE AND MIXED BITS THAT HAVEN'T BEEN SET YET AND RETURN WHETHER NODE IS MIXED
if (mask) {
this->value[offset] = setBits(this->value[offset], mask, value);
this->mixed[offset] &= ~mask;
}
return this->mixed[offset] != 0 || this->value[offset] != 0 && this->value[offset] != 0xFFFF;
}
bool check(uint32_t a, uint32_t b, uint16_t value = 0xFFFF, uint8_t bits = 28, uint32_t offset = 0) {
uint8_t posA = a >> bits, posB = b >> bits;
uint16_t maskA = 1 << posA, maskB = 1 << posB;
uint16_t mask = maskB ^ (maskA - 1) ^ (maskB - 1);
// IF NODE IS LEAF: CHECK BITS A TO B INCLUSIVE AND RETURN
if (bits == 0) {
return (this->value[offset] & mask) == (value & mask);
}
uint32_t subMask = ~(0xFFFFFFFF << bits);
a &= subMask; b &= subMask;
// IF SUB-RANGE A IS MIXED AND PART OF IT NEEDS CHECKING: RECURSE AND RETURN IF FALSE
if ((this->mixed[offset] & maskA) && (a != 0 || posA == posB && b != subMask)) {
if (this->check(a, posA == posB ? b : subMask, value, bits - 4, offset * 16 + posA + 1)) {
mask ^= maskA;
}
else return false;
}
// IF SUB-RANGE B IS MIXED AND PART OF IT NEEDS CHECKING: RECURSE AND RETURN IF FALSE
if (posA != posB && (this->mixed[offset] & maskB) && b != subMask) {
if (this->check(0, b, value, bits - 4, offset * 16 + posB + 1)) {
mask ^= maskB;
}
else return false;
}
// CHECK INBETWEEN BITS (AND A AND/OR B IF NOT YET CHECKED) WHETHER SOLID AND CORRECT
return (this->mixed[offset] & mask) == 0 && (this->value[offset] & mask) == (value & mask);
}
public:
NaryTree32() { // CONSTRUCTOR: INITIALISES ROOT NODE
this->value[0] = 0x0000;
this->mixed[0] = 0x0000;
}
void addValue(uint32_t a) {this->set(a, a);}
void addRange(uint32_t a, uint32_t b) {this->set(a, b);}
void delValue(uint32_t a) {this->set(a, a, 0);}
void delRange(uint32_t a, uint32_t b) {this->set(a, b, 0);}
bool hasValue(uint32_t a) {return this->check(a, a);}
bool hasRange(uint32_t a, uint32_t b) {return this->check(a, b);}
bool notValue(uint32_t a) {return this->check(a, a, 0);}
bool notRange(uint32_t a, uint32_t b) {return this->check(a, b, 0);}
};
int main() {
NaryTree32 *tree = new NaryTree32();
tree->addRange(4294967280, 4294967295);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
tree->delValue(4294967290);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
tree->addRange(1000000000, 4294967295);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
tree->delRange(2000000000, 4294967280);
std::cout << tree->hasRange(4294967280, 4294967295) << "\n";
return 0;
}
我很惊讶没有人建议 segment trees 存储值的整数域。 （当用于 2d 和 3d 图形等几何应用程序时，它们分别称为四叉树和八叉树。）插入、删除和查找的时间和 space 复杂度与 (maxval - minval) 中的位数成正比)，即log_2(maxval - minval)，整数数据域的最大值和最小值。
简而言之，我们在 [minval, maxval] 中编码一组整数。最顶层 0 的节点代表整个范围。每个连续级别的节点代表 sub-ranges 的近似大小 (maxval - minval) / 2^k。当包含一个节点时，它对应值的某些子集是表示集的一部分。当它是一片叶子时，它的 all 个值都在集合中。当它不存在时，none 是。
例如如果minval=0且maxval=7，则k=0节点的k=1children表示[0..3]和[4..7]。它们在k=2层的children是[0..1][2..3][4..5]和[6..7]，k=3个节点代表单个元素。集合 {[1..3], [6..7]} 将是树（从左到右的级别）：
[0..7] -- [0..3] -- [0..1]
| | `-[1]
| `- [2..3]
` [4..7]
`- [6..7]
不难看出树的 space 将是 O(m log (maxval - minval))，其中 m 是存储在树中的间隔数。
使用带动态插入和删除的线段树并不常见，但事实证明算法相当简单。需要注意确保节点数量最少。
这里是一些经过简单测试的 java 代码。
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class SegmentTree {
// Shouldn't differ by more than Long.MAX_VALUE to prevent overflow.
static final long MIN_VAL = 0;
static final long MAX_VAL = Long.MAX_VALUE;
Node root;
static class Node {
Node left;
Node right;
Node(Node left, Node right) {
this.left = left;
this.right = right;
}
}
private static boolean isLeaf(Node node) {
return node != null && node.left == null && node.right == null;
}
private static Node reset(Node node, Node left, Node right) {
if (node == null) {
return new Node(left, right);
}
node.left = left;
node.right = right;
return node;
}
/**
* Accept an arbitrary subtree rooted at a node representing a subset S of the range [lo,hi] and
* transform it into a subtree representing S + [a,b]. It's assumed a >= lo and b <= hi.
*/
private static Node add(Node node, long lo, long hi, long a, long b) {
// If the range is empty, the interval tree is always null.
if (lo > hi) return null;
// If this is a leaf or insertion is outside the range, there's no change.
if (isLeaf(node) || a > b || b < lo || a > hi) return node;
// If insertion fills the range, return a leaf.
if (a == lo && b == hi) return reset(node, null, null);
// Insertion doesn't cover the range. Get the children, if any.
Node left = null, right = null;
if (node != null) {
left = node.left;
right = node.right;
}
// Split the range and recur to insert in halves.
long mid = lo + (hi - lo) / 2;
left = add(left, lo, mid, a, Math.min(b, mid));
right = add(right, mid + 1, hi, Math.max(a, mid + 1), b);
// Build a new node, coallescing to leaf if both children are leaves.
return isLeaf(left) && isLeaf(right) ? reset(node, null, null) : reset(node, left, right);
}
/**
* Accept an arbitrary subtree rooted at a node representing a subset S of the range [lo,hi] and
* transform it into a subtree representing range(s) S - [a,b]. It's assumed a >= lo and b <= hi.
*/
private static Node del(Node node, long lo, long hi, long a, long b) {
// If the tree is null, we can't remove anything, so it's still null
// or if the range is empty, the tree is null.
if (node == null || lo > hi) return null;
// If the deletion is outside the range, there's no change.
if (a > b || b < lo || a > hi) return node;
// If deletion fills the range, return an empty tree.
if (a == lo && b == hi) return null;
// Deletion doesn't fill the range.
// Replace a leaf with a tree that has the deleted portion removed.
if (isLeaf(node)) {
return add(add(null, lo, hi, b + 1, hi), lo, hi, lo, a - 1);
}
// Not a leaf. Get children, if any.
Node left = node.left, right = node.right;
long mid = lo + (hi - lo) / 2;
// Recur to delete in child ranges.
left = del(left, lo, mid, a, Math.min(b, mid));
right = del(right, mid + 1, hi, Math.max(a, mid + 1), b);
// Build a new node, coallescing to empty tree if both children are empty.
return left == null && right == null ? null : reset(node, left, right);
}
private static class NotContainedException extends Exception {};
private static void verifyContains(Node node, long lo, long hi, long a, long b)
throws NotContainedException {
// If this is a leaf or query is empty, it's always contained.
if (isLeaf(node) || a > b) return;
// If tree or search range is empty, the query is never contained.
if (node == null || lo > hi) throw new NotContainedException();
long mid = lo + (hi - lo) / 2;
verifyContains(node.left, lo, mid, a, Math.min(b, mid));
verifyContains(node.right, mid + 1, hi, Math.max(a, mid + 1), b);
}
SegmentTree addRange(long a, long b) {
root = add(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
return this;
}
SegmentTree addVal(long a) {
return addRange(a, a);
}
SegmentTree delRange(long a, long b) {
root = del(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
return this;
}
SegmentTree delVal(long a) {
return delRange(a, a);
}
boolean containsVal(long a) {
return containsRange(a, a);
}
boolean containsRange(long a, long b) {
try {
verifyContains(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
return true;
} catch (NotContainedException expected) {
return false;
}
}
private static final boolean PRINT_SEGS_COALESCED = true;
/** Gather a list of possibly coalesced segments for printing. */
private static void gatherSegs(List<Long> segs, Node node, long lo, long hi) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
if (PRINT_SEGS_COALESCED && !segs.isEmpty() && segs.get(segs.size() - 1) == lo - 1) {
segs.remove(segs.size() - 1);
} else {
segs.add(lo);
}
segs.add(hi);
} else {
long mid = lo + (hi - lo) / 2;
gatherSegs(segs, node.left, lo, mid);
gatherSegs(segs, node.right, mid + 1, hi);
}
}
SegmentTree print() {
List<Long> segs = new ArrayList<>();
gatherSegs(segs, root, MIN_VAL, MAX_VAL);
Iterator<Long> it = segs.iterator();
while (it.hasNext()) {
long a = it.next();
long b = it.next();
System.out.print("[" + a + "," + b + "]");
}
System.out.println();
return this;
}
public static void main(String [] args) {
SegmentTree tree = new SegmentTree()
.addRange(0, 4).print()
.addRange(6, 7).print()
.delVal(2).print()
.addVal(5).print()
.addRange(0,1000).print()
.addVal(5).print()
.delRange(22, 777).print();
System.out.println(tree.containsRange(3, 20));
}
}