Formal golang implementation of Sqrt (Square Root) Decomposition

Here you can find the an implementation on a simple sqrt decomposition algorithm, but do you need it? Here’s the formal condition:

Then you can use it.

If UnionQ and query functions are Θ(1), then the complexity of the algoritm in average and worst case is Θ(Q*sqrt(N)) where Q is the number of queries.

MO’s algorithm

If UnionQ function is hard, but there exist an efficient function expandQ: Q, E -> Q (I’ll skip the formality) then you can use MO’s algorithm with complexity in average and worst case as Θ((N+Q)*sqrt(N)).

In the same repo you can find an implementation on this too.