Function smawk::online_column_minima

pub fn online_column_minima<T: Copy + PartialOrd, M: Fn(&[(usize, T)], usize, usize) -> T>(
    initial: T,
    size: usize,
    matrix: M,
) -> Vec<(usize, T)>

Compute upper-right column minima in O(m + n) time.

The input matrix must be totally monotone.

The function returns a vector of (usize, T). The usize in the tuple at index j tells you the row of the minimum value in column j and the T value is minimum value itself.

The algorithm only considers values above the main diagonal, which means that it computes values v(j) where:

v(0) = initial
v(j) = min { M[i, j] | i < j } for j > 0

If we let r(j) denote the row index of the minimum value in column j, the tuples in the result vector become (r(j), M[r(j), j]).

The algorithm is an online algorithm, in the sense that matrix function can refer back to previously computed column minima when determining an entry in the matrix. The guarantee is that we only call matrix(i, j) after having computed v(i). This is reflected in the &[(usize, T)] argument to matrix, which grows as more and more values are computed.