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.
Описание
CiteSeerX — Counting Inversions, Offline Orthogonal Range Counting, and Related Problems
%0 Generic
%1 Chan_countinginversions
%A Chan, Timothy M.
%A Patrascu, Mihai
%D 2009
%K inversions_number kendall_tau_distance
%T Counting Inversions, Offline Orthogonal Range Counting, and Related Problems
%U https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.208.2715
%X 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.
@misc{Chan_countinginversions,
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. },
added-at = {2020-01-13T13:20:02.000+0100},
author = {Chan, Timothy M. and Patrascu, Mihai},
biburl = {https://www.bibsonomy.org/bibtex/2826d4cd9ebcc335735367b261d38e55f/mkf},
description = {CiteSeerX — Counting Inversions, Offline Orthogonal Range Counting, and Related Problems},
interhash = {3507f33a6affbda98b56fa2ade188e6f},
intrahash = {826d4cd9ebcc335735367b261d38e55f},
keywords = {inversions_number kendall_tau_distance},
timestamp = {2020-01-13T13:20:02.000+0100},
title = {Counting Inversions, Offline Orthogonal Range Counting, and Related Problems},
url = {https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.208.2715},
year = 2009
}