File SequenceQueries.h

↰ Parent directory (ADS/algorithm)

Questions on a sequence that a sort or a single scan answers faster than the comparison of all the pairs: the smaller items on the right of each item, the longest run with few distinct items, the longest stretch that a set of intervals leaves uncovered, and the cheapest matching of two sets of points on a line.

Definition (ADS/algorithm/SequenceQueries.h)

Detailed Description

  • smallerToTheRight(): for each place i, the number of places j > i with A[ j ] < A[ i ], by mergesort on the places [see File MergeSort.h]: when an item of the left half goes to the output, the items of the right half gone before it are exactly the smaller ones on its right in that half, and the halves below added the others; :math:` O( n log n ) ` time and :math:` O( n ) ` space, against the :math:` Theta( n^2 ) ` of the double loop. Equal items do not count, since the left one goes first. The sum of the counts is the number of inversions [see countInversions()]; a Fenwick tree on the ranks gives the same counts in :math:` O( n log n ) ` by a scan from the right;

  • longestKDistinctRun(): the first longest run of consecutive items with at most k distinct values, by a window whose right end advances one place at a time and whose left end advances while the window holds more than k values, with the counts of its values in a search tree; each end moves n times, :math:` O( n log k ) `;

  • largestGap(): the longest stretch between the first start and the last end of a set of closed intervals [ a , b ] covered by none of them, the first one on ties: the intervals by start, and a gap wherever a start is beyond the farthest end so far, the union of intervals by a sweep; :math:` O( n log n ) `;

  • lineAssignment(): the least sum of :math:` | h_i - l_{pi( i )} | ` over the matchings :math:` pi ` of two sets of n points on a line, both sorted and matched in order: if :math:` h_1 le h_2 ` and :math:` l_1 le l_2 ` the crossed matching never costs less than the straight one, an exchange argument; :math:` O( n log n ) , against the :math: O( n^3 ) ` of the Hungarian method on general costs. The same order is optimal for any convex function of the difference, the optimal transport on the line.

The contracts [see File Contract.h]: the counts of smallerToTheRight() sum to the inversions of A (an audit); the run of longestKDistinctRun() has at most k values (an audit); the intervals of largestGap() must have a <= b, and its gap meets none of them (an audit); lineAssignment() needs two sets of the same size. The functions are defined in SequenceQueries.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, Esercizi Divide-et-impera, Raccolte da compiti scritti

    1. Fenwick, A new data structure for cumulative frequency tables, Software: Practice and Experience 24(3), 327-336, 1994, doi:10.1002/spe.4380240306

    1. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly 2(1-2), 83-97, 1955, doi:10.1002/nav.3800020109

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions