Algorithm to find frequency of a number in an array within range l to r

Revision en1, by OneClickAC, 2017-06-13 11:52:08

Hello codeforces community, I was solving this problem ( on codeforces and came across an interesting doubt (at least according to me) . I just wanted to know that is there any algorithm for finding frequency of any number in a particular range in an array?

We use Mo`s Algorithm for finding max frequency in a range but is there any other one which is faster for this particular problem of mine (calculating frequency of any number)?

I tried writing an algorithm for it but I believe its too slow to pass in one second. Although I think that my build takes O (n log n) time and queries come out in O (log n) time but I believe it's the uncertainty of hashing that`s making the algorithm slower.

Here is my code —

Note- Please do not tell me the solutions of the codeforces problem. I have already read the editorial and their implementation is pretty simple. I just want to get an answer for my curiosity to be able to learn a new beautiful algorithm (if there is) and help some other learners like me.


  Rev. Lang. By When Δ Comment
en1 English OneClickAC 2017-06-13 11:52:08 1171 Initial revision (published)