I tried to solve this question but suddenly a question strike to my mind what if we have to find the value of ONLY F(L,R,X) L and R are the indexes of the array and X=The element whose frequency we have to determined . one solution which strike to me is like..just take map< long long,vector >mp,and for each element of the given array just insert its corresponding index at that location for example if arr[]=[2,3,4,5,2,2].So mp[2]={0,5,6},mp[3]={3},mp[4]={2} and so on... and just take lower bound and upper bound of the value of L and R in mp[x]. So it will give us answer in NO of Query * O(log(abs(R-L+1)).

But Can some one please suggest me **how can i can calculate ONLY F(L,R,X) by using SEGMENT TREE** Proble Link.....

Thanks In Advance..!!

Auto comment: topic has been updated by shailesh_24 (previous revision, new revision, compare).If you don't require updates you can do it in O(log(MAX)) by using persistent segment trees covering the range [1, MAX] and giving the frequency to each value.

If you do require updates you can do it in O(log^2(n)) by using a normal segment tree that has an order statistics set in each segment. Counting frequency of X is just order_of_key(X+1) — order_of_key(X).

itu Counting frequency of X is just order_of_key(X+1) — order_of_key(X). could you please elaborate it more..??

I'm talking about the order statistics set data structure. You can implement it with a binary search tree where each node knows how many nodes there are in its subtree. It's basically the structure that directly solves this problem: http://www.spoj.com/problems/ORDERSET/ (though you can solve this problem easily offline).

For implementation details, you can use a treap instead of avl/red-black, or you can use the GNU version: http://codeforces.com/blog/entry/11080

Hi, I understood your query part but how to update in such a segment tree considering I am dealing with range updates (adding x from l to r).

I would do something simpler like sqrt decomposition in such a case, if there's enough time.

Can you explain it a little more?

I mean , how to perform range update in time?

use persistent range tree which is built by value.

u need to lazy create it i think.

sounds

To be more specificly,

Spoiler!rt[i] represent the root of the i-th range tree

each time u insert(rt[i],rt[i-1],x,1);

which means + 1 on that spot

then u just parallel binary search.

If it is wrong plz figure it out and that would be appreciate :)