c++ - 线段树的构建

Question

给定一个包含 n 个元素的整数数组 A 和 m 个查询，每个查询包含一个整数 x 我必须回答数组中小于 x 的元素数。 0 < A[i] < 10^6 && x < 10^6

例子:

A[]={105,2,9,3,8,5,7,7}

查询

6

8

104

回答

3

5

7

解释:

对于 query1 元素是={2,3,5}

对于 query2 元素是={2,3,5,7,7}

对于 query3 元素是={2,9,3,8,5,7,7}

问题:

How to solve this question using segment tree?(我已经构建了线段树来查找范围内的最大值、最小值和总和，但我的脑子一片空白如何为此构建线段树)。请举例说明

注意:我已经知道使用排序和二进制搜索(针对每个查询)的 nlogn 解决方案。我想了解如何利用线段树来解决这个问题。

谢谢

Answer 1

如果您为数组的元素 构建线段树，我认为线段树不会起作用 A .您可以对段使用最大和最小值的一些启发式/修剪，但最终对于像

这样的情况

0, 10^6, 0, 10^6, 0, 10^6,...

查询将退化为 O(n) ，因为你需要深入到每一片叶子中。

你应该做的是在可能值的范围上构建一个线段树:对于每个值0<a<10^6你还记得数组 A 中有多少个具有这个值的元素吗？ .例如对于

A=[5,2,3,3,3,5,7,7] 

出现的数组将是

f=[0,0,1,3,0,2,0,1,0,...]

现在查询数组中的元素数 A小于x , 转换为对出现数组 f 中的元素总和 的查询来自 0直到 x .

您可以使用线段树来回答此查询。

但是，如果您在查询之前知道整个数组 - 这是一个非常无聊的情况 - 您可以只使用 prefix sum在阵列上 f有预处理时间 O(n)及查询时间O(1) .

线段树只有在查询和更新数组A 时才有意义是交错的。

如果查询和更新交错，我建议使用 Fenwicktree ，它不像线段树那样灵活，但它正是为这类问题量身定做的。它更容易实现，速度更快，需要的内存更少。