CODEWITHSUNDEEP
algorithmdata-structuresbinary-indexed-tree
Diego Becquer
Diego Becquer

Reputation: 81

Answer queries about the number of distinct numbers in a given range

The problem

I have an array with N numbers. The numbers may be disctints and may also be unordered. I have to answer Q queries about how many distinct numbers there are between A and B. Where A, B are indices between 0 <= A <= B < array.Length.

I know how to do it O(N) per query by using a HashTable but I'm asking for a more efficient solution. I tried to improve it with sqrt decomposition and also with a segment tree but I couldn't. I'm not showing any code because I did not find any idea that worked. I'm looking for someone to give an explanation of a faster solution.

UPDATE

I read you can collect the queries and then answer them all by using a Binary Indexed Tree (BIT). Can someone explain how to do it. Assume I know how a BIT works.

Upvotes: 1

Views: 515

Answers (1)

RiaD
RiaD

Reputation: 47650

For each index i find the previous index prev[i] that has the same value (or -1 if there's no such index). It may be done in O(n) average by going left to right with hash_map, then the answer for range [l;r) of indices is number of elements i in range [l;r) such that their value is less then l (it require some thinking but should be clear)

Now we will solve problem "given range [l;r) and value c find number of elements that are less then c" on array prev. It may be done in O(log^2) using segment tree, if we save in each vertex all the numbers that are in its range(subtree). (On each query we will get O(log n) vertices and do binary search in them)

Upvotes: 1

Related Questions