Number of occurrences of a number in a particular range?

Question

Given a large unsorted array, I need to find out the number of occurrences of a given number in a particular range. (There can be many queries)

e.g. if arr[]={ 6,7,8,3,4,1,2,4,6,7,8,9} and left_range=3 and right_range=7 and number=4, then the output will be 2. (considering a 0 indexed array)

arr[i] can be in the range of 1 to 100000. The array can have up to 100000 numbers.

Can you guide me about which data structure or algorithm I should use here?

PS: Pre-processing the array is allowed.

Answer 1

Here's a solution that doesn't require segment tree.

Preprocessing:

1. For each number arr[i], push i to the 2D vector(or ArrayList) with index arr[i].

Answering Queries:

For any query do a binary search on vector[num] to find the index of the maximum index of num in that vector that's less than or equal to right range, let's call it R. Then find the minimum index that's greater than or equal to left range, let's call it L. Print R - L + 1

Runtime: Preprocessing in O(1) per item, taking total O(N) time. Per Query answer: O(lg(N))

Space: Quite linear assuming vector or ArrayList