How to calculate the product of frequencies of different elements of an array efficiently?

Revision en1, by LovesProgramming, 2019-06-12 13:54:43

Warning:-This is a beginner's/newbie's doubt so don't read further and waste your precious time if you are not interested :-)

I am new to Codeforces, so please don't down-vote. I'll delete the topic if needed.

We are given an array and I have to calculate the product of frequencies of numbers in a particular range of the array i,e. [L,R].

How to do it?

My approach:- Say, [1,2,2,2,45,45,4]. L=2 and R=6. Answer=3(frequency of 2)*2(frequency of 45)=6.

Just traverse the array and put the frequencies of each number in a map; finally multiply all those values. Is there any better method to do this for multiple range queries online?

Do we require persistence ?

Tags complexity optimization, #persistence

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English LovesProgramming 2019-06-12 13:54:43 774 Initial revision (published)