arrays - 范围 (l, r) 中小于 'x' 的元素数

Question

给定一个整数数组，并且存在单一类型的查询。

查询 - (L, R, X)

在 (L, R) 范围内找到小于 'X' 的元素。

PS：所有查询都是事先提供的，即我们需要设计一个离线算法来回答所有查询。

Answer 1

这可以在段树和向量的帮助下完成。在分段树的每个节点处维护一个向量。在构建树时，在段树的每个节点处保持向量中的排序顺序。

应用二分搜索在处理查询的段树的每个节点处查找小于“X”的元素数。

int count = upper_bound(v.begin(), v.end(), X) - v.begin();

是否可以查询 O(lg N) 范围内不同整数的数量？

上面的帖子也很好地描述了这个想法。