Introduction to MO’s Algorithm Pattern

You are given an array and many queries. Each query names a range and asks how many distinct values it contains.

[1, 2, 1, 3, 2]
range 0 to 2  ->  values 1, 2, 1  ->  2 distinct
range 1 to 4  ->  values 2, 1, 3, 2  ->  3 distinct

Prefix sums answered range questions in one subtraction. They cannot answer this one. Distinct counts do not subtract, because the same value may appear on both sides of the split.

Answering each query directly costs O(N), so Q queries cost O(N × Q).

Now compare two of those queries. Ranges 0 to 2 and 1 to 4 overlap heavily