我有一个数组（可以有2X10 ^ 5个值）。我想对该数组执行大量查询。每个查询的类型均为[L，R]，并且查询的结果应该是子数组中从索引L到索引R的唯一值的数量。
我知道这可以在O（nrootn）
时间内使用Mo的算法完成。但是，要抓住的是Mo的算法是离线算法。我要寻找的是一种在线算法，因为上一个查询的结果决定了我的情况下的下一个查询。我试图用来形成一个分割树，节点将在其中存储范围内所有不同的元素。但是，对于我的目的而言，这太慢了。这种方法预处理花费了太多时间。
编辑：
所以这是实际的问题。我有一个大小为N的数组，可以有重复的值。我想执行查询以确定给定子数组中不同值的数量。在每个查询中，我收到两个值X
和Y。现在要找到我必须为其确定唯一值数量的子数组[L，R]，我必须计算L = X xor ans和R = Y xor ans，其中ans是上一个查询的结果（如果为0，则为[是第一个查询）。 我有一个数组（可以有2X10 ^ 5个值）。我想对该数组执行大量查询。每个查询的类型均为[L，R]，查询的结果应为唯一的数量...
这是我的C ++尝试使用here解决方案（也发布在Wavelet tree中），并使用从https://www.geeksforgeeks.org/wavelet-trees-introduction改编的代码实现。重新构造问题的想法（作为Photon commented的链接）是首先构造一个数组，该数组列出原始数组中每个对应的单元格，并向右列出下一个重复元素的索引。然后问题就来了，找出间隔中有多少个单元格具有超出当前间隔的“下一个索引”（显然这些间隔内没有重复项），可以用修饰的小波树来查询。请参阅底部的（基于非零的）查询示例。