线段树：小于x的数的数量

Question

我正在尝试解决 this 问题。

我发现 tutorial 这个问题，但我不知道如何构建线段树，它会在 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)，但这不是必需的。