algorithm - 二叉索引树实现以计算给定间隔内小于给定数的整数数？

Question

给定一个数组，我如何计算和存储在给定间隔内小于给定数的元素数。

例如如果数组是 {2 6 3 5 2} 并且给出的是区间 {2 4} 并且整数是 6 那么答案应该是 3
3 5 2 都小于 6。

请看间隔从 1 开始。

早些时候，我尝试使用线段树来做这件事，但无法想出任何解决方案。

谁能建议可以做什么？

我也尝试阅读 BIT 上的 topcoder 教程。

是否有任何经典算法可以做到这一点。

Answer 1

假设我们正在尝试访问数据库以查找价格在给定时间间隔内低于给定数字的时间。

离线处理

如果您有许多可以一起处理的查询，那么您可以使用这种方法:

For each query for an interval between a and b, store a and b in a sorted dictionary that maps from the important times (a and b) to the query

For each price in time order:
    Add the price to a Binary Indexed Tree (BIT) 
    Use the sorted dictionary to find all queries that can now be answered
    For each of these queries use the BIT to count the number of elements less than the number

这在 O( (n+q)(log(q)+log(n)) ) 中回答查询，其中 n 是元素的数量，q 是查询的数量

在线处理

如果您有需要一次处理一个的传入查询，那么您可以考虑使用 KD-tree将元素存储在可以快速搜索的二维数据结构中。