algorithm - 检查静态数组是否不包含给定范围元素的数据结构

我在数据结构课的下列作业问题上被困了好几个小时：从{1，，，可以得到n个整数的静态集s（即s永不改变）。……，u}。描述一个o（n log u）大小的数据结构，它可以在o（1）时间内回答以下查询：Empty(i, j)-当且仅当s中没有介于i和j之间的元素（其中i和j是{1中的整数）时返回true。……，u}）。一开始我想用y-fast-trie。使用y-fast-trie可以实现o（n）空间和o（logloglogu）查询（通过查找i的后继项并检查其是否大于j）。但是o（loglogu）不是o（1）……然后我想也许我们可以对数组进行排序，并创建第二个数组，大小为n+1，数组中没有的范围，然后在查询中，我们会检查[i，j]是否是其中一个范围的子范围，但我没有想到任何方法可以使用o（nlogu）空间并在o（1）中回答查询。我不知道如何解决这个问题，我觉得我甚至还没有接近解决方案，任何帮助都会很好。 最佳答案 我们可以创建一个X快速的S（取O（nLogu）空间），并在每个节点中保存其子树中叶子的最大值和最小值。现在我们可以用它来回答o（1）中的空查询。这样地：空的（i，j）我们首先计算x or（i，j）现在这个数字中的前导零的个数是i和j共享的前导位的个数，我们把这个数字标记为k。现在我们取i的第一个k位（或j，因为它们相等）并检查x-fast-trie哈希表，如果有一个节点等于这些位。如果没有，我们将返回true，因为i和j之间的任何数字也将具有相同的k前导位，并且由于没有任何数字具有这些前导位，因此i和j之间没有任何数字。如果有，我们将该节点标记为x。如果X->右->最小＞J和X->左->最大对不起，英语不好关于algorithm - 检查静态数组是否不包含给定范围元素的数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57312129/