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..!!
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.net/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?
ignore
use persistent range tree which is built by value.
u need to lazy create it i think.
sounds
To be more specificly,
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 :)
It can be solved in O((n+q)*sqrt(n)) where n is lenght of array and q is number of querys: Make groups with lenght sqrt(n). lets denote g(i,j) the number of indexes k in group j such that a[k]=i; we can easily count this in O(n*sqrt(n)). then for query in each i group that is in range L,R plus to answer g(X,i)(this groups will be at most sqrt(n)) and for indexes that are not in this group and we can see all this indexes and compare with i(this indexes will be at most 2*sqrt(n)). so we can answer each query in O(sqrt(n)) time;
this can work if you do updates too(O(1) for each update)