algorithm - 段树：小于 x 的数字数量

Question

我正在尝试解决这个问题。

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

谁能解释我该怎么做？

Answer 1

这很简单：

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

2. 要回答查询，请将查询段分解为O(log n)节点（与标准 min/max/sum 段树的方法相同）并对存储在每个节点中的数组运行二进制搜索以找到更少的元素数量比x。它为O(log^2 n)每个查询提供时间。您也可以O(log n)使用分数级联来实现，但这不是必需的。