Abstract
We give an O(n √ lg n)-time algorithm for counting the number of inversions in a permutation on n elements. This improves a long-standing previous bound of O(n lg n / lg lg n) that followed from Dietz’s data structure WADS’89, and answers a question of Andersson and Petersson SODA’95. As Dietz’s result is known to be optimal for the related dynamic rank problem, our result demonstrates a significant improvement in the offline setting. Our new technique is quite simple: we perform a “vertical partitioning ” of a trie (akin to van Emde Boas trees), and use ideas from external memory. However, the technique finds numerous applications: for example, we obtain • in d dimensions, an algorithm to answer n offline orthogonal range counting queries in time O(n lg d−2+1/d n); • an improved construction time for online data structures for orthogonal range counting; • an improved update time for the partial sums problem; • faster Word RAM algorithms for finding the maximum depth in an arrangement of axis-aligned rectangles, and for the slope selection problem. As a bonus, we also give a simple (1 + ε)-approximation algorithm for counting inversions that runs in linear time, improving the previous O(n lg lg n) bound by Andersson and Petersson.
Users
Please
log in to take part in the discussion (add own reviews or comments).