arshad2117's blog

How to find frequency of a given element in a range?
By arshad2117, history, 8 years ago, In English

Given an array A of n elements and queries of type (l r k),find the number of occurrences of k in the range l to r

If there are no updates, we can solve the problem by having a map<int,vector> and doing a binary search.

But what if there are updates involved.

I read somewhere that we can use bit..

But I am not sure how that would be useful

Thank you in advance

  • Vote: I like it
  • +9
  • 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

Auto comment: topic has been updated by arshad2117 (previous revision, new revision, compare).

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

You can use SQRT decomposition. Time complexity is O(q*sqrt(n)*lg(n)+n*lg(n)).

You can also do it offline and compress the numbers in queries, and the time complexity would be O(q*sqrt(n)+n).

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

    Can you please elaborate or provide some relevant link?

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

      I don't have any links, let's wait for the others to respond.

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

    Batman please explain how to compress numbers in queries. this is new for me.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      for(int i=0;i<n;i++)cin>>a[i],b[i]=a[i];
sort(b,b+n);
new_n=unique(b,b+n)-b;

      Now you can use lower_bound(b,b+new_n,x) to find where x is.

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

You can use de merge sorte tree, that is, a segmente tree where each node is a sorted vector(from l to r), the in each query you just do a lower bound an a upper bound. https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorial

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +45 Vote: I do not like it

You can do update and query in , using map<int, Tree>, where Tree is Treap/AVL/Red-black/... tree.

→ Reply