是的，即使您应该在线回答查询，也可以在O（log n）中执行此操作。但是，这需要一些相当复杂的技术。
首先，让我们解决以下问题：给定一个数组，回答形式为“索引[l，r]中有多少个<=
x”的查询。这是通过类似于段树的结构完成的，有时也称为“合并排序树”。它基本上是一个分段树，其中每个节点都存储一个排序的子数组。此结构需要O（n log
n）个内存（因为存在log n个层，并且每个层都需要存储n个数字）。它也是内置在O（n log
n）中的：您只需自下而上，并为每个内部顶点合并其子级的排序列表。
这是一个例子。假设
1 5 2 6 8 4 7 1是原始数组。
|1 1 2 4 5 6 7 8||1 2 5 6|1 4 7 8||1 5|2 6|4 8|1 7||1|5|2|6|8|4|7|1|
现在您可以回答O（log ^ 2 n次）中的那些查询：只需对段树进行遍历查询（遍历O（log n）节点）并进行二进制搜索即可知道有多少个<=
x在该节点中（从此处添加O（log n））。
使用分数级联技术可以将速度提高到O（log
n），该技术基本上允许您不在每个节点中执行二进制搜索，而只能在根目录中执行二进制搜索。但是，它足够复杂，无法在帖子中进行描述。
现在我们回到原来的问题。假设您有一个数组a_1，…，a_n。生成另一个数组b_1，…，b_n，其中b_i
=数组中下一个出现的a_i的索引；如果是最后一个出现，则为∞。
示例（1索引）：
a = 1 3 1 2 2 1 4 1b = 3 ∞ 6 5 ∞ 8 ∞ ∞
现在让我们计算[l，r]中的数字。对于每个唯一数字，我们将计算其在细分中的最后一次出现。使用b_i概念，您可以看到数字的出现是当且仅当时才是最后一次`b_i
r`。因此，问题归结为“段[l，r]中有多少个数> r”，这被微不足道地简化为我上面所描述的。
希望能帮助到你。
