1个回答
5
很简单：
1. 存储一组特定节点所涵盖的数字范围的排序数组（初始化需要 O(n * log n) 的时间和空间）。
2. 要回答查询，将查询段分解为 O(log n) 个节点（与标准 min/max/sum 段树相同的方式），并在每个节点中运行二分查找以找到小于 x 的元素数量。每次查询需要 O(log^2 n) 的时间。您也可以使用分数级联实现 O(log n)，但这不是必需的。
1. 存储一组特定节点所涵盖的数字范围的排序数组（初始化需要 O(n * log n) 的时间和空间）。
2. 要回答查询，将查询段分解为 O(log n) 个节点（与标准 min/max/sum 段树相同的方式），并在每个节点中运行二分查找以找到小于 x 的元素数量。每次查询需要 O(log^2 n) 的时间。您也可以使用分数级联实现 O(log n)，但这不是必需的。
- kraskevich
2
我们如何在nlogn的时间复杂度内完成1的操作？排序范围中有n^2个元素。存储排序结果本身将需要n^2的空间复杂度。 - cegprakash
1@cegprakash 因为线段树不存储所有范围，所以有O(n log n)个元素。它有O(log n)级别，每个元素在每个级别上只出现一次。一个朴素的排序需要O(n log^2 n)，但我们可以对每个连续的级别使用归并排序，使其变为O(n log n)。 - kraskevich
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接