rmq

Overview ¶

Package rmq implements a range-minimum-query data structure that 1. precomputes a sparse table on O(N*logN) time 2. answers the minimum value of any subarray of a static array in O(1) time.

Example usage.

q := NewRMQ[int]([]int{6, 1, 0, 10, 9}, func(v1, v2 int) bool { return v1 < v2 })
q.RMQ(0, 0) // 6
q.RMQ(0,1) // 1

See https://cp-algorithms.com/sequences/rmq.html for more info.