Tom*_*erg 19 algorithm big-o data-structures
我在数据结构类的以下作业问题上呆了几个小时：
从{1，。。得到n个整数的静态集合S（即S永不改变）。。。，u}。
描述大小为O（n log u）的数据结构，该数据结构可以在O（1）时间内回答以下查询：
Empty(i, j)-当且仅当S中没有元素介于i和j之间（其中i和j是{1，...，u}中的整数）时，-才返回TRUE。
起初，我想到了使用y-fast-trie。
使用y-fast-trie我们可以实现O（n）空间和O（loglogu）查询（通过找到i的后继者并检查它是否大于j）。
但是O（loglogu）不是O（1）...
然后，我想也许我们可以对数组进行排序，并创建第二个大小为n + 1的范围的数组，该范围不在数组中，然后在查询中检查[i，j]是否为以下项之一的子范围范围，但我没有想到使用O（nlogu）空间并且可以在O（1）中回答查询的任何方法。
我不知道如何解决这个问题，而且我觉得我甚至还没有找到解决方案，任何帮助都很好。
我们可以创建一个S的x-fast-trie（占用O（nlogu）空间），并在每个节点中保存其子树中叶子的最大值和最小值。现在我们可以用它来回答O（1）中的Empty查询。像这样：
Empty（i，j）我们首先计算xor（i，j），现在该数字中前导零的数目将是i和j共同共享的前导比特数，我们将其标记为k。现在，我们将获取i的前k个位（或j，因为它们相等），然后检查x-fast-trie哈希表是否存在等于这些位的节点。如果没有，我们将返回TRUE，因为i和j之间的任何数字也将具有相同的k个前导位，并且由于这些前导位没有任何数字，因此i和j之间没有任何数字。如果存在，我们将该节点标记为X。
如果X-> right-> minimum> j和X-> left-> maximum <i，我们返回TRUE，否则返回FALSE，因为如果为false，则i和j之间存在一个数字，如果为true，则所有小于j的数字也小于i，所有大于i的数字也大于j。
对不起，英语不好