Struct SqrtDecomposition

sqrt/sqrtdecomposition.go:21–29

Sqrt (or Square Root) Decomposition is a technique used for query an array and perform updates Inside this package is described its most simple data structure, you can find more at: https://cp-algorithms.com/data_structures/sqrt_decomposition.html Formally, You can use SqrtDecomposition only if: G

// - (Only if you want use $update$ function)
// $\forall n\in \N > 0, E_1,..., E_n\in E \\ query(E_1,...,E_{new},..., E_n)=updateQ(query(E_1,...,E_{old},...,E_n), indexof(E_{old}), E_{new})$
type SqrtDecomposition[E any, Q any] struct {
	querySingleElement func(element E) Q
	unionQ             func(q1 Q, q2 Q) Q
	updateQ            func(oldQ Q, oldE E, newE E) (newQ Q)

	elements  []E
	blocks    []Q
	blockSize uint64
}

// Create a new SqrtDecomposition instance with the parameters as specified by SqrtDecomposition comment
// Assumptions: