1

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.

Diego Becquer
  • 81
  • 6
  • 2
    What do you mean by `different numbers` in between A and B. If it's about how many numbers ie. range, then Why not just Use `B-A-1` – C0deDaedalus Jan 07 '18 at 05:58
  • 2
    If you have a list, and two arbitrary numbers, and you want to find the numbers in the list between those two numbers, you can use binary search, with a time complexity of `O(logn)`. [This](https://stackoverflow.com/a/46980453/3483203) is a great answer to get you started. – user3483203 Jan 07 '18 at 06:09
  • @chrisz It's asking for the amount of **distinct** numbers, which can't be done in less than O(n) (since any given element can be a duplicate or distinct, thus we need to look at every element) if it needs to be done from scratch (that is, if the question were asking for 1 instead of Q queries). – Bernhard Barker Jan 07 '18 at 15:55
  • I edited the question. Thanks – Diego Becquer Jan 07 '18 at 17:11
  • 3
    You can find something here: https://apps.topcoder.com/forums/?module=RevisionHistory&messageID=1369039 But it's true there is not a proper explanation, this is more an efficient working code. – Raudel Ravelo Jan 07 '18 at 17:33
  • @chrisz can you read again? I updated the text – Diego Becquer Jan 10 '18 at 08:12
  • Wait you just want to know based on indices? So like in a length 10 array, how many unique numbers fall between the second and eighth index? – user3483203 Jan 10 '18 at 16:16

1 Answers1

1

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)

RiaD
  • 46,822
  • 11
  • 79
  • 123