Given index i,j(j>=i) How to find the frequency of a A[j] at a subarray(i,j)?

Question

Given an array A of integers , I am trying to find out at a given position j , how many times A[j] occurs from every i=0 to i=j in A. I have devised a solution like below

map<int,int> CF[400005];
for(int i=0;i<n;++i)
{
   cin>>A[i];
   if(i!=0)
      CF[i-1] = CF[i];
   ++CF[i][A[i]]; 
}

than I can answer each query in logn time. But this procedure uses too much memory. Is there any way of doing it using less memory?

for more clarification , you can see the problem I am trying to solve http://codeforces.com/contest/190/problem/D

Answer 1

Create an array B of the same size as A and a map C. For each j in B[j] keep track of the number of occurrences of A[j] before j. In C keep track of the last occurrence of given element. Then you answer queries in constant time and it requires just O(n) memory.

Sorry for my pseudo-C++.

map<int,int> C;
int B[n]; // zeros

for(int i=0;i<n;++i)
{
    cin >> A[i];
    int prev = C[A[i]]; // let me assume it gives -1 if no element

    if (pref == -1) // this is the fist occurrence of B[i]
        B[i] = 1;
    else // if not the first, then add previous occurrences
        B[i] = B[prev] + 1 

    C[A[i]] = i; // keep track where the last info about A[j] is
}

Answer 2

Didn't give this too much time, but maybe instead of using a map will all the positions, use a list where for each element you put the points where the count of that element changes, something towards this:

struct count_info
{
    int index;
    int count;
    count_info* next;
};
...
std::map<int, count_info*> data;

, and then look up the right position in that queue. You still need one map, but then underneath you would only have a list of these pointers, and on query you look-up the A[i] in the map, and then go through the list while i > index && next && i < next->index. Of course, if logn is a must then this fails because the list look-up is n at worst.