### 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 161-173 |

Number of pages | 13 |

State | Published - May 6 2010 |

Externally published | Yes |

Event | 21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States Duration: Jan 17 2010 → Jan 19 2010 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 21st Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | Austin, TX |

Period | 1/17/10 → 1/19/10 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Counting inversions, offline orthogonal range counting, and related problems'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 161-173). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).