Static Range Minimum Query

Question 1

Colored Range Query Problem
Given (static) A[1, n] of colors (integers), Distinct(i, j) returns all distinct colors in A[i, …, j] in time proportional to the number of distinct colors

Answer 1

Let’s say K = number of distinct colors

With Segment Tree: store in each node the answer of its segment. Θ(klogn) because we may have logn nodes with k elements

Let’s have an arrow for every distinct element that points to the previous occurrence of the same element in the same array or to -1. Count the arrows that points to elements in positions before the interval starting position.

Question 2

Given A[1, n] of colors, answer Q queries offline.
3OrMore(i, j) = reports #colors that occur at least 3 times in A[i, …, j]

Answer 2

The idea of MO’s algorithm is to pre-process all queries so that result of one query can be used in next query. Sqrt Decomposition is a method (or a data structure) that allows you to perform some common operations (finding sum of the elements of the sub-array, finding the minimal/maximal element, etc.) in Θ(sqrt(n)) operations, which is much faster than Θ(n) for the trivial algorithm.

There exists an ordering of the queries.
* split in sqrt(n) groups by groupping queries based on their starting position
* sort queries in each group by their ending poisition
* solve the groups in any order but solve queries in each group by increasing ending position

Groups can be implicitly done by just sorting all the queries by using a comparator such that, given two intervals, compares by ending position if the intervals belong to the same group, otherwise it compares according to the group they belong.

Solve queries by using the partial result got from the previous query and by removing or adding positions that are not or are in the current query.

• Alligning current left index takes Θ(sqrt(n)) for each query in the group. Overall Θ(|group| * sqrt(n))
• Alligning current right index takes overall Θ(n) time because the queries are sorted by ending position

Summing up: Θ(sum_each_group(|group| * sqrt(n) + n)) = Θ(Q*sqrt(n) + n * sqrt(n)) = Θ((Q+n)) * sqrt(n))

Question 3

Given A[1, n] positive integers, answer Q offline queries.
query(i, j) = it asks for set of distinct elements in range and number of occurrences of an element in that range

Target time complexity: Θ((n+q) * sqrt(n)) time. It is independent of the number of distinct elements

Answer 3

This problem cannot be solved with Segment Tree because otherwise the time spent to compute the answer will be proportional to the number of elements you are counting.

Solve with Mo’s algorithm

Question 4

Static Range Minimum Query