Documentation
¶
Overview ¶
Package sparsetable implements a sparse table.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type RMQpm1 ¶ added in v0.2.0
type RMQpm1[T constraints.Integer] struct { // contains filtered or unexported fields }
RMQpm1 represents a special case of RMQ. All neighbour elements should differ in 1. Allows to answer rmq queries in constant time with linear preprocessing time.
func NewRMQpm1 ¶ added in v0.2.0
func NewRMQpm1[T constraints.Signed](elements []T) RMQpm1[T]
NewRMQpm1 returns RMQpm1 struct. All neighbour elements should differ in 1.
type SparseTable ¶
type SparseTable[T any] struct { // contains filtered or unexported fields }
SparseTable represents a sparse table. Zero value of SparseTable is invalid sparse table, should be used only with New().
func New ¶
func New[T any](op func(T, T) T, elements []T) *SparseTable[T]
New returns an initialized sparse table. op should be idempotent, commutative and associative.
func (*SparseTable[T]) Query ¶
func (s *SparseTable[T]) Query(l, r int) T
Query returns result of operation on elements[l:r+1].
Source Files
Click to show internal directories.
Click to hide internal directories.