lie*_* wu 5 java arrays algorithm segment-tree
所以这是一个问题，我给了一个整数数组，它的数字都是不同的，假设它是
int[] data = {21, 34, 12, 88, 54, 73};
现在我想看看子数组或范围是否包含一个范围内的数字（也给出了）。换句话说，我想查看数组的某个范围是否包含某个范围内的数字。例如，如果我有一个函数，check(int a, int b, int l, int r)其中a和b是数组的范围，l并且r是数字的范围。
因此，对于上面的数组，check(0, 2, 20, 50)应该返回true，因为 from index = 0 to 2，有21, 34, 12，并且有两个数字 ，21, 34在 的范围内20 to 50。
所以另一个例子是应该check(2, 3, 20, 80)返回，false因为 ,12, 88没有 20, 80 范围内的数字。
我正在考虑使用线段树，因为据我所知，RMQ（范围最小查询）可以通过使用线段树来解决，因此我认为线段树也可以解决这个问题；"get" function然而，线段树的全部都是"single"（也许不是最好的词），所以，我想知道线段树应该保存哪些节点。是否有任何算法可以回答每个查询，而O(log(n))不是"build" time，O(n^2)数组n的大小在哪里？
注意：使用线段树只是我自己的想法，任何其他方法都值得赞赏。
这有点奇怪，但是持久的红黑树，或者任何其他自平衡树的持久变体，都可以。
持久数据结构允许人们（时间和空间）有效地在不同时间拍摄该结构的“快照”，然后稍后查询这些快照，并根据截至快照时间的结构状态接收结果。对于此用例，我们想要执行的特定查询是对给定范围内包含的所有元素进行计数（如果O(log n)每个节点都用其后代的数量进行注释，则可以执行此操作）。
在这种情况下，您将从一个空结构开始，在时间i插入data[i]快照，然后将其存储为snapshot[i]。然后，check(a,b,l,r)将被实现为return snapshot[b].countInRange(l,r) > snapshot[a].countInRange(l,r). 也就是说，如果截至 time 的目标范围中的元素数量多于b截至 time 的a元素数量，则目标范围中的某些元素必须已添加到a和之间b，从而满足您的约束。
如果以最佳方式实现，预计算将花费时间O(n log n)和空间O(n)，并且查询将花费时间O(log n)。
如果您愿意放宽O(log n)查询要求，则更简单且可能更实用的方法是二维kD 树。只需将每个data[i]作为点插入(i, data[i])，然后进行范围搜索即可a<=x<b, l<=y<r。这为您提供了 的查询时间O(sqrt(n))，虽然效率不高，但更容易编写代码（或查找现有代码）。