shailesh_24's blog

Frequency of a number in the given range.....[L,R]
By shailesh_24, history, 8 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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://mirror.codeforces.com/blog/entry/11080

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        Can you explain it a little more?

        I mean , how to perform range update in time?

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ignore

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

use persistent range tree which is built by value.

u need to lazy create it i think.

sounds

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To be more specificly,

    Spoiler!

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

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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)

→ Reply