列表中大于给定整数的整数数量可能不在日志日志时间列表中
Number of integers in a list larger than a given integer possibly not in the list in log log time
给定一个包含 n 个非负整数的无序列表（不保证分布或重复），我希望能够给出一个可能不在列表中的整数，并以至少那么大的整数数作为响应在列表中。我有多达 n^2 的预处理时间，以及多达 n*log(n) 的存储空间。这可能吗？
我不够好的解决方案是二进制搜索（log n 时间，常量 space）。
在地图中存储所有可能查询的地图会占用太多存储空间。
编辑：需要对输入进行一些假设（例如整数的分布或最大大小）的部分解决方案也很有用。
编辑：这被称为 predecessor/successor 问题。 Beame & Fich 在一篇论文中构建了一个数据结构，在 O(n) space 中存储来自大小为 N 的宇宙的 n 个整数元素集，并在 O(min{(log log N ) / (log log log N), sqrt(log n / (log log n))}) time.
http://homes.cs.washington.edu/~beame/papers/stocpred.pdf
编辑 - 赏金：截至今天上午，None 的答案正是我要找的。 N 不受限制。整数不一定低于 32 位。最大的元素可能远大于元素的数量。我假设输入没有分配。在现有的答案中，我接受了 Coffin 的赏金，因为它涵盖了我确实有分布的相对较大的问题子集。
根据您的参数，您可以尝试 https://en.wikipedia.org/wiki/Van_Emde_Boas_tree - "a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O(log m) time, or equivalently in O(log log M) time, where M=2^m is the maximum number of elements that can be stored in the tree."（注意文章顶部的警告，指出其伪代码中存在错误）
（注意：此答案是在 OP 删除他对 templatetypedef 的评论之前发布的："As for integer size, we can assume 32 bit unsigned."）
准备一个指向 65536 个排序桶的散列集（从技术上讲，这是 O(1) 额外的 space，尽管我们可以说列表中有大约 5500 个元素代表阈值，高于该阈值 space 将小于您规定的 n * log n)。每个键代表您分配的 32 位中最左边 16 位的可能配置。每个存储桶将存储当前存储桶上方的元素数量，以及该整数范围内的列表值和重复项的计数（如有必要）。
插入时，所有较低的桶计数值都需要更新；从技术上讲，O(1) 更新时间，尽管对于较小的列表来说显然很重要；但是如果列表是预先知道的，正如你所建议的，预处理时间可以是 O(n * log n) 乘以 "reporting" 从桶到桶的自上而下的计数。查询将花费 O(1) 时间来查找存储桶。桶中的查找最多需要 log m，其中桶中元素的数量 m 小于或等于 65536，这是一个独立于 n.[=18 的常量=]
通过预处理，根据范围和分布，可以使用两个或三个偏移哈希来进一步优化。
假设您的元素分布相当均匀（或者至少相当接近地遵循 一些 分布）显而易见的方法是对数据进行排序，然后使用插值搜索而不是二分查找。
内插搜索通常具有大致 O(log log n) 复杂度。
哦，如果从名字上看不太明显的话，插值搜索的基本思想就是通过插值来猜测你要搜索的元素的大概位置。例如，如果您要处理 0 到 100,000 之间的整数，并且您需要找到 21,000，您可以从数组中大约 21% 的位置开始，而不是从中点开始。然后，根据你在那里找到的值，你可以使用插值来找到更好的猜测，等等。
该示例适用于线性插值，但相同的基本思想同样适用于其他分布——您只需使用适合（相当好地）数据分布的函数。
（注意：此答案是在 OP 删除他对 templatetypedef 的评论之前发布的："As for integer size, we can assume 32 bit unsigned."）
Dan Willard 发明的 Y-fast trie (https://en.m.wikipedia.org/wiki/Y-fast_trie) 支持您正在寻找的操作类型和时间复杂度。它使用 O(n) space 和 O(log log U) 渐近查找时间，其中 U 是域中的最大值，出于我们的目的，它可能是您列表中的最大值；这意味着在列表中包含超过 32 个元素的常规二分搜索已经渐近变慢了。
Y-fast trie 由 n / log U 二叉搜索树构成，它们一起包含整个排序列表作为一个序列；和一个 X-fast trie (https://en.m.wikipedia.org/wiki/X-fast_trie)，其中包含每个二叉搜索树的代表，以便查找要搜索的树。
我将描述一些我学到的东西（因为我只学了一点）关于 X-fast trie 的 successor/predecessor 查找方法，您似乎对这种操作感兴趣。渐近时间复杂度为查找是 O(log log U).
k 的 predecessor/successor 的查找从对高度为 log U 的 trie 的级别进行二进制搜索开始。我们从 trie 的一半开始 - 如果对应于该级别的长度 k 的前缀不在 trie 的散列节点中，则 k 的祖先必须在上面，否则在下面。
一旦找到祖先，我们就知道该节点的一个子树有叶子（叶子是存储 trie 值的地方），但另一个 k 本来应该在的地方没有。这是访问巧妙的 descendant pointer 的地方，它在左子树缺失时指向右子树中的最小叶子，或者在右子树缺失时指向左子树中最大的叶子。
我们现在直接位于 k 的前导或后继，并且可以报告 trie 的存储值：要在哪个二叉树中搜索。渐近 space 复杂度：O(n + n / log U * log U) = O(n)。渐近时间复杂度：O(log log U + log log U) = O(log log U)
如果预处理时间和 space 足以将数据放入树中，您可以创建一个排序树，其中每个分支存储有多少叶子连接到其右侧（大于）。在构建树时，在插入新叶子时，可以为您在右侧传递的每个分支递增此计数，因此不会花费（很多）额外时间。获取大于或等于某个整数的值的数量可以通过找到整数在树中的位置，并将您在途中通过的左侧分支的所有计数相加来完成。
时间复杂度是树类型的常规复杂度加上构造期间每个叶子的几个值增量，space 是常规的 space 加上每个叶子的计数器，其大小取决于最大叶子数。
在示例代码中我使用了一个简单的二叉树；您可以使用剩余的预处理时间来平衡树的高度（确保计数已更新），或使用某种自平衡树类型（但这可能会过于复杂）。
Javascript 中的示例代码片段：（使用 100,000 个随机整数；正确处理树中不存在的重复值和搜索值）
function ChopTree() {
this.root = null;
this.insert = function(value) {
var branch = null, leaf = this.root, before;
while (leaf != null) {
branch = leaf;
before = value <= leaf.value;
if (before) leaf = branch.left
else {
++branch.count;
leaf = branch.right;
}
}
if (branch == null) this.root = new Leaf(value)
else if (before) branch.left = new Leaf(value)
else branch.right = new Leaf(value);
}
this.chop = function(axe) {
var branch = this.root, count = 0;
while (branch != null) {
if (axe <= branch.value) {
count += branch.count;
branch = branch.left;
}
else branch = branch.right;
}
return count;
}
function Leaf(value) {
this.value = value;
this.left = null;
this.right = null;
this.count = 1;
}
}
var t = new ChopTree();
for (var i = 0; i < 100000; i++) t.insert(Math.floor(Math.random() * 4294967296));
document.write("Inserted 100,000 random integers from 0 to 2<SUP>32</SUP><BR><BR>");
document.write(t.chop(0) + " greater than or equal to 0<BR>");
document.write(t.chop(2147483648) + " greater than or equal to 2<SUP>31</SUP><BR>");
document.write(t.chop(4000000000) + " greater than or equal to 4×10<SUP>9</SUP><BR>");
document.write(t.chop(4294967296) + " greater than or equal to 2<SUP>32</SUP><BR>");
更新：增加计数值可用于处理重复值，如果您期望有很多重复值并且 space 是一个问题。
（注意：此答案是在 OP 删除他对 templatetypedef 的评论之前发布的："As for integer size, we can assume 32 bit unsigned."）
Y-fast trie（参见我的其他答案）可以让我们达到 O(log log U + log log U) 查找时间，这意味着如果您的范围是数十亿，我们实际上正在寻找 5 + 5 = 10 次迭代每次查找。
但是有一种方法可以实现 5 次迭代的实际查找时间。
对最左边 17 位的所有组合进行哈希处理。将这 131,072 个键指向最大高度 15 和最大 space m * 15 的 X-fast 尝试（参见我的其他答案），其中 m 是此特定存储桶中的元素数。尝试将仅包含列表中每个适当元素的最右边的 15 位。由于这些 X-fast 尝试的大小受到限制，因此查找时间将达到最大值 1 + log 15 = 5。如果您的列表少于 32,768 个元素，space 实际上是 131,072 + n * 15，比您要求的 n * log n 多一点；但是因为哈希和最大 trie 高度是常数，渐近 space 复杂度实际上是 O(n)，并且对于 32,768 个或更多元素的列表，space-复杂度实际上会小于 n * log n.
这是 X-fast 树 JavaScript 中的粗略草图：
function pad(width, string, padding) {
return (width <= string.length)
? string
: pad(width, padding + string, padding);
}
function makeXFastTree(elems){
var xfast = {};
var height = Math.floor(Math.log2(Math.max.apply(null, elems))) + 1;
function insert(x){
var y = pad(height,x.toString(2),'0');
var l = 1;
var d = y.substr(-l,1);
// add element to the parent node
if (!xfast[y.substr(0,height - l)]){
xfast[y.substr(0,height - l)] = [y,y];
} else if (d == '1'){
xfast[y.substr(0,height - l)][1] = y;
} else {
xfast[y.substr(0,height - l)][0] = y;
}
// update higher nodes
l++;
d = y.substr(-l,1);
var temp = y.substr(0,height - l);
while (temp.length > 0){
if (!xfast[temp]){
xfast[temp] = d == 0 ? ['0',y] : [y,'1'];
} else if (d == '0'){
xfast[temp][0] = '0';
if (xfast[temp][1] != '1' && y > xfast[temp][1]){
xfast[temp][1] = y;
}
} else {
xfast[temp][1] = '1';
if (xfast[temp][0] != '0' && y < xfast[temp][0]){
xfast[temp][0] = y;
}
}
l++;
d = y.substr(-l,1);
temp = y.substr(0,height - l);
}
}
for (var i=0; i<elems.length; i++){
insert(elems[i]);
}
return [xfast,height];
}
function find(T,height,x){
var y = pad(height,x.toString(2),'0');
var l = d = height >> 1;
var temp = y.substr(0,l);
while (true){
// ancestor found
if (T[temp] && !T[y.substr(0,temp.length + 1)]){
return T[temp];
}
d = Math.ceil(d/2);
if (T[temp]){
l += d;
temp = y.substr(0,l);
} else {
l -= d;
temp = y.substr(0,l);
}
}
}
输出：
var t = makeXFastTree([31,27,10,5,4,2,1]);
console.log(JSON.stringify(t[0]));
{"0":["0","1"],"1":["11011","1"],"11":["0","1"],"110":["11011","1"],"111":["11111","1"]
,"1101":["11011","11011"],"1111":["11111","11111"],"0101":["01010","01010"]
,"010":["01010","1"],"01":["0","01010"],"0010":["00100","00101"],"001":["0","00101"]
,"00":["0","1"],"0001":["00010","00010"],"000":["0","1"],"0000":["00001","00001"]}
console.log(find(t[0],t[1],28));
["11111", "1"]
console.log(find(t[0],t[1],3));
["00010", "00010"]
整数限制为 32 位，这个问题没有多大意义。事实上，如果 N 小于 2^32，那么它是有界的，渐近复杂性没有意义。
如果 N 是无界的，那么您可以对值进行排序并在线性时间内计算它们的重数。这样，元素的数量再次受到限制，渐近复杂性不再有意义。
问题陈述中存在缺陷。
给定一个包含 n 个非负整数的无序列表（不保证分布或重复），我希望能够给出一个可能不在列表中的整数，并以至少那么大的整数数作为响应在列表中。我有多达 n^2 的预处理时间，以及多达 n*log(n) 的存储空间。这可能吗？
我不够好的解决方案是二进制搜索（log n 时间，常量 space）。
在地图中存储所有可能查询的地图会占用太多存储空间。
编辑：需要对输入进行一些假设（例如整数的分布或最大大小）的部分解决方案也很有用。
编辑：这被称为 predecessor/successor 问题。 Beame & Fich 在一篇论文中构建了一个数据结构，在 O(n) space 中存储来自大小为 N 的宇宙的 n 个整数元素集，并在 O(min{(log log N ) / (log log log N), sqrt(log n / (log log n))}) time.
http://homes.cs.washington.edu/~beame/papers/stocpred.pdf
编辑 - 赏金：截至今天上午，None 的答案正是我要找的。 N 不受限制。整数不一定低于 32 位。最大的元素可能远大于元素的数量。我假设输入没有分配。在现有的答案中，我接受了 Coffin 的赏金，因为它涵盖了我确实有分布的相对较大的问题子集。
根据您的参数，您可以尝试 https://en.wikipedia.org/wiki/Van_Emde_Boas_tree - "a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O(log m) time, or equivalently in O(log log M) time, where M=2^m is the maximum number of elements that can be stored in the tree."（注意文章顶部的警告，指出其伪代码中存在错误）
（注意：此答案是在 OP 删除他对 templatetypedef 的评论之前发布的："As for integer size, we can assume 32 bit unsigned."）
准备一个指向 65536 个排序桶的散列集（从技术上讲，这是 O(1) 额外的 space，尽管我们可以说列表中有大约 5500 个元素代表阈值，高于该阈值 space 将小于您规定的 n * log n)。每个键代表您分配的 32 位中最左边 16 位的可能配置。每个存储桶将存储当前存储桶上方的元素数量，以及该整数范围内的列表值和重复项的计数（如有必要）。
插入时，所有较低的桶计数值都需要更新；从技术上讲，O(1) 更新时间，尽管对于较小的列表来说显然很重要；但是如果列表是预先知道的，正如你所建议的，预处理时间可以是 O(n * log n) 乘以 "reporting" 从桶到桶的自上而下的计数。查询将花费 O(1) 时间来查找存储桶。桶中的查找最多需要 log m，其中桶中元素的数量 m 小于或等于 65536，这是一个独立于 n.[=18 的常量=]
通过预处理，根据范围和分布，可以使用两个或三个偏移哈希来进一步优化。
假设您的元素分布相当均匀（或者至少相当接近地遵循 一些 分布）显而易见的方法是对数据进行排序，然后使用插值搜索而不是二分查找。
内插搜索通常具有大致 O(log log n) 复杂度。
哦，如果从名字上看不太明显的话，插值搜索的基本思想就是通过插值来猜测你要搜索的元素的大概位置。例如，如果您要处理 0 到 100,000 之间的整数，并且您需要找到 21,000，您可以从数组中大约 21% 的位置开始，而不是从中点开始。然后，根据你在那里找到的值，你可以使用插值来找到更好的猜测，等等。
该示例适用于线性插值，但相同的基本思想同样适用于其他分布——您只需使用适合（相当好地）数据分布的函数。
（注意：此答案是在 OP 删除他对 templatetypedef 的评论之前发布的："As for integer size, we can assume 32 bit unsigned."）
Dan Willard 发明的 Y-fast trie (https://en.m.wikipedia.org/wiki/Y-fast_trie) 支持您正在寻找的操作类型和时间复杂度。它使用 O(n) space 和 O(log log U) 渐近查找时间，其中 U 是域中的最大值，出于我们的目的，它可能是您列表中的最大值；这意味着在列表中包含超过 32 个元素的常规二分搜索已经渐近变慢了。
Y-fast trie 由 n / log U 二叉搜索树构成，它们一起包含整个排序列表作为一个序列；和一个 X-fast trie (https://en.m.wikipedia.org/wiki/X-fast_trie)，其中包含每个二叉搜索树的代表，以便查找要搜索的树。
我将描述一些我学到的东西（因为我只学了一点）关于 X-fast trie 的 successor/predecessor 查找方法，您似乎对这种操作感兴趣。渐近时间复杂度为查找是 O(log log U).
k 的 predecessor/successor 的查找从对高度为 log U 的 trie 的级别进行二进制搜索开始。我们从 trie 的一半开始 - 如果对应于该级别的长度 k 的前缀不在 trie 的散列节点中，则 k 的祖先必须在上面，否则在下面。
一旦找到祖先，我们就知道该节点的一个子树有叶子（叶子是存储 trie 值的地方），但另一个 k 本来应该在的地方没有。这是访问巧妙的 descendant pointer 的地方，它在左子树缺失时指向右子树中的最小叶子，或者在右子树缺失时指向左子树中最大的叶子。
我们现在直接位于 k 的前导或后继，并且可以报告 trie 的存储值：要在哪个二叉树中搜索。渐近 space 复杂度：O(n + n / log U * log U) = O(n)。渐近时间复杂度：O(log log U + log log U) = O(log log U)
如果预处理时间和 space 足以将数据放入树中，您可以创建一个排序树，其中每个分支存储有多少叶子连接到其右侧（大于）。在构建树时，在插入新叶子时，可以为您在右侧传递的每个分支递增此计数，因此不会花费（很多）额外时间。获取大于或等于某个整数的值的数量可以通过找到整数在树中的位置，并将您在途中通过的左侧分支的所有计数相加来完成。
时间复杂度是树类型的常规复杂度加上构造期间每个叶子的几个值增量，space 是常规的 space 加上每个叶子的计数器，其大小取决于最大叶子数。
在示例代码中我使用了一个简单的二叉树；您可以使用剩余的预处理时间来平衡树的高度（确保计数已更新），或使用某种自平衡树类型（但这可能会过于复杂）。
Javascript 中的示例代码片段：（使用 100,000 个随机整数；正确处理树中不存在的重复值和搜索值）
function ChopTree() {
this.root = null;
this.insert = function(value) {
var branch = null, leaf = this.root, before;
while (leaf != null) {
branch = leaf;
before = value <= leaf.value;
if (before) leaf = branch.left
else {
++branch.count;
leaf = branch.right;
}
}
if (branch == null) this.root = new Leaf(value)
else if (before) branch.left = new Leaf(value)
else branch.right = new Leaf(value);
}
this.chop = function(axe) {
var branch = this.root, count = 0;
while (branch != null) {
if (axe <= branch.value) {
count += branch.count;
branch = branch.left;
}
else branch = branch.right;
}
return count;
}
function Leaf(value) {
this.value = value;
this.left = null;
this.right = null;
this.count = 1;
}
}
var t = new ChopTree();
for (var i = 0; i < 100000; i++) t.insert(Math.floor(Math.random() * 4294967296));
document.write("Inserted 100,000 random integers from 0 to 2<SUP>32</SUP><BR><BR>");
document.write(t.chop(0) + " greater than or equal to 0<BR>");
document.write(t.chop(2147483648) + " greater than or equal to 2<SUP>31</SUP><BR>");
document.write(t.chop(4000000000) + " greater than or equal to 4×10<SUP>9</SUP><BR>");
document.write(t.chop(4294967296) + " greater than or equal to 2<SUP>32</SUP><BR>");
更新：增加计数值可用于处理重复值，如果您期望有很多重复值并且 space 是一个问题。
（注意：此答案是在 OP 删除他对 templatetypedef 的评论之前发布的："As for integer size, we can assume 32 bit unsigned."）
Y-fast trie（参见我的其他答案）可以让我们达到 O(log log U + log log U) 查找时间，这意味着如果您的范围是数十亿，我们实际上正在寻找 5 + 5 = 10 次迭代每次查找。
但是有一种方法可以实现 5 次迭代的实际查找时间。
对最左边 17 位的所有组合进行哈希处理。将这 131,072 个键指向最大高度 15 和最大 space m * 15 的 X-fast 尝试（参见我的其他答案），其中 m 是此特定存储桶中的元素数。尝试将仅包含列表中每个适当元素的最右边的 15 位。由于这些 X-fast 尝试的大小受到限制，因此查找时间将达到最大值 1 + log 15 = 5。如果您的列表少于 32,768 个元素，space 实际上是 131,072 + n * 15，比您要求的 n * log n 多一点；但是因为哈希和最大 trie 高度是常数，渐近 space 复杂度实际上是 O(n)，并且对于 32,768 个或更多元素的列表，space-复杂度实际上会小于 n * log n.
这是 X-fast 树 JavaScript 中的粗略草图：
function pad(width, string, padding) {
return (width <= string.length)
? string
: pad(width, padding + string, padding);
}
function makeXFastTree(elems){
var xfast = {};
var height = Math.floor(Math.log2(Math.max.apply(null, elems))) + 1;
function insert(x){
var y = pad(height,x.toString(2),'0');
var l = 1;
var d = y.substr(-l,1);
// add element to the parent node
if (!xfast[y.substr(0,height - l)]){
xfast[y.substr(0,height - l)] = [y,y];
} else if (d == '1'){
xfast[y.substr(0,height - l)][1] = y;
} else {
xfast[y.substr(0,height - l)][0] = y;
}
// update higher nodes
l++;
d = y.substr(-l,1);
var temp = y.substr(0,height - l);
while (temp.length > 0){
if (!xfast[temp]){
xfast[temp] = d == 0 ? ['0',y] : [y,'1'];
} else if (d == '0'){
xfast[temp][0] = '0';
if (xfast[temp][1] != '1' && y > xfast[temp][1]){
xfast[temp][1] = y;
}
} else {
xfast[temp][1] = '1';
if (xfast[temp][0] != '0' && y < xfast[temp][0]){
xfast[temp][0] = y;
}
}
l++;
d = y.substr(-l,1);
temp = y.substr(0,height - l);
}
}
for (var i=0; i<elems.length; i++){
insert(elems[i]);
}
return [xfast,height];
}
function find(T,height,x){
var y = pad(height,x.toString(2),'0');
var l = d = height >> 1;
var temp = y.substr(0,l);
while (true){
// ancestor found
if (T[temp] && !T[y.substr(0,temp.length + 1)]){
return T[temp];
}
d = Math.ceil(d/2);
if (T[temp]){
l += d;
temp = y.substr(0,l);
} else {
l -= d;
temp = y.substr(0,l);
}
}
}
输出：
var t = makeXFastTree([31,27,10,5,4,2,1]);
console.log(JSON.stringify(t[0]));
{"0":["0","1"],"1":["11011","1"],"11":["0","1"],"110":["11011","1"],"111":["11111","1"]
,"1101":["11011","11011"],"1111":["11111","11111"],"0101":["01010","01010"]
,"010":["01010","1"],"01":["0","01010"],"0010":["00100","00101"],"001":["0","00101"]
,"00":["0","1"],"0001":["00010","00010"],"000":["0","1"],"0000":["00001","00001"]}
console.log(find(t[0],t[1],28));
["11111", "1"]
console.log(find(t[0],t[1],3));
["00010", "00010"]
整数限制为 32 位，这个问题没有多大意义。事实上，如果 N 小于 2^32，那么它是有界的，渐近复杂性没有意义。
如果 N 是无界的，那么您可以对值进行排序并在线性时间内计算它们的重数。这样，元素的数量再次受到限制，渐近复杂性不再有意义。
问题陈述中存在缺陷。