### shailesh_24's blog

By shailesh_24, history, 19 months ago, ,

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.....

•
• +2
•

 » 19 months ago, # |   0 Auto comment: topic has been updated by shailesh_24 (previous revision, new revision, compare).
 » 19 months ago, # |   0 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).
•  » » 19 months ago, # ^ |   +1 itu Counting frequency of X is just order_of_key(X+1) — order_of_key(X). could you please elaborate it more..??
•  » » » 19 months ago, # ^ |   +6 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
•  » » 13 months ago, # ^ |   0 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).
•  » » » 13 months ago, # ^ |   0 I would do something simpler like sqrt decomposition in such a case, if there's enough time.
•  » » » » 13 months ago, # ^ | ← Rev. 5 →   0 Can you explain it a little more?I mean , how to perform range update in time?
 » 19 months ago, # | ← Rev. 2 →   0 use persistent range tree which is built by value.u need to lazy create it i think.sounds
•  » » 19 months ago, # ^ |   0 To be more specificly, Spoiler!rt[i] represent the root of the i-th range treeeach time u insert(rt[i],rt[i-1],x,1); which means + 1 on that spotthen u just parallel binary search.If it is wrong plz figure it out and that would be appreciate :)