第k小元素范围查询算法

摘要

范围查询是进行数据分析的有效方法,预计算技术可以提高查询的速度,从而实现快速的用户响应.rn 提出了一个新的范围查询问题:第k小元素范围查询,迄今未见有文献报导.在决策支持系统中,了解第k小元素比仅仅依靠最大值要关键得多.在线段树、扩展红黑树及预计算的基础上,给出了查询第k小元素的算法,其空间复杂度为0(nlogn),查询的时间复杂度为0(log3n).