Bad*_*adf 5 algorithm segment-tree
我正试图解决这个问题.
我找到了这个问题的教程但是我没有得到如何构建分段树,它将在O(log n)中找到小于x的数字(x可以改变).在教程中它已被省略.
任何人都可以解释我该怎么做？
这很简单:
将所有数字的排序数组存储在特定节点覆盖的范围内
(O(n * log n)内存和初始化时间).
要回答查询,请将查询段分解为O(log n)节点(与标准最小/最大/总和段树的方式相同),并对存储在每个节点中的数组运行二进制搜索,以查找较少的元素数比x.它为O(log^2 n)每个查询提供时间.您也可以O(log n)使用分数级联来实现,但这不是必需的.