algorithm - 线段树 : amount of numbers smaller than x

Question

我正在尝试解决 this问题。

我找到了 tutorial对于这个问题，但我不知道如何构建线段树，它会在 O(log n) 中找到小于 x 的数字量(x 可以更改)。在教程中它已被省略。

谁能告诉我怎么做？

Answer 1

很简单:

1. 存储特定节点覆盖范围内所有数字的排序数组
   (O(n * log n)内存和初始化时间)。

2. 要回答查询，将查询段分解为 O(log n) 节点(与标准最小/最大/总和段树的处理方式相同)并运行对存储在每个节点中的数组进行二进制搜索，以查找小于 x 的元素数。它为每个查询提供 O(log^2 n) 时间。您也可以使用分数级联实现 O(log n)，但这不是必需的。