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

Question

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

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

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

Answer 1

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

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

因此，假设我们有数组 [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 分别是查询的数量和输入数组中的元素数量。