给定一个n个元素的整数数组A和m个查询，每个查询包含一个整数x，我必须回答数组中小于x的元素数。
0
例:
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}
题:
如何使用分段树解决这个问题？(我已经建立了分段树来查找某个范围内的最大值，最小值和总和，但是我的想法是空白如何为此建立分段树)。请用示例进行解释
注意:我已经知道使用排序和二进制搜索(针对每个查询)的nlogn解决方案。我想学习如何利用段树来解决这个问题。
谢谢
最佳答案
我不认为如果为数组 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中的元素总数。
您可以使用细分树来回答此查询。
但是，如果您在查询之前就知道了整个数组(这是一个很无聊的情况)，则可以在数组f上使用prefix sum以及预处理时间O(n)和查询时间O(1)。
仅当交错查询和更新A数组时，分段树才有意义。
如果查询和更新是交错的，我建议使用Fenwicktree，它不像段树那么灵活，但是正是针对此类问题而量身定制的。它更易于实现，更快并且需要更少的内存。
关于c++ - 段树的 build ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35418422/