在给定范围内查找大于x的元素数

Question

给定一个包含n个元素的数组,如何在给定范围索引i中找到大于或等于给定值(x)的元素个数到O(log n)复杂度中的索引j？

查询的形式为(i,j,x),这意味着从数组中的第i个到第j个元素中查找大于x的元素数

数组未排序.i,j&x对于不同的查询是不同的.数组的元素是静态的.编辑:i,j,x对于不同的查询都可以是不同的!

Answer 1

如果我们事先知道所有查询,我们可以通过使用Fenwick树来解决这个问题.

首先,我们需要根据它们的值对数组和查询中的所有元素进行排序.

因此,假设我们有数组[5,4,2,1,3]和查询(0,1,6)和(2,5,2),我们将在排序后得到以下结果:[1,2,2] ,3,4,5,6]

现在,我们需要按降序处理每个元素:

• 如果我们遇到一个来自数组的元素,我们将在Fenwick树中更新它的索引,它取O(log n)

• 如果我们遇到查询,我们需要在查询的这个范围内检查树中添加了多少元素,这些元素占用O(log n).

对于上面的示例,该过程将是:

  1st element is a query for value 6, as Fenwick tree is empty -> result is 0
  2nd is element 5 -> add index 0 into Fenwick tree
  3rd element is 4 -> add index 1 into tree.
  4th element is 3 -> add index 4 into tree.
  5th element is 2 -> add index 2 into tree.
  6th element is query for range (2, 5), we query the tree and get answer 2.
  7th element is 1 -> add index 3 into tree. 
  Finish.

因此,总的来说,我们的解决方案的时间复杂度是O((m + n)log(m + n)),m和n分别是来自输入数组的查询数和元素数.