Abstract:

The K-th number query is a fundamental problem in computer algorithm，which is a subroutine of numerous problems.Researchers have done a lot of further work including the linear time algorithm for single K-th number query.The time complexity O（lb n） for each query solution has already been found for the multi-queries K-th number query problem，with the help of balance search tree structure.But the BST-based algorithm is not very easy to implement as well as a big constant factor hidden in the Big-O representation.This paper introduces an algorithm based on Bit Indexed Tree to tackle K-th number query with easy implementation and small constant factor.Finally，the experiment shows that the new algorithm is remarkably faster than previous algorithms with nearly optimal memory usage.