Different Approaches to query: number of distinct elements from [L,R]
Difference between en2 and en3, changed 0 character(s)
Problem: Given an array answer queries(online) of the form [L,R]=number of distinct elements in the array from index L to R.↵

What different approaches/solutions are there to this problem.↵

Few approaches I know/heard of:↵

1.Using Segment/Merge-Sort tree (link:https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n)↵

2.Modified Sqrt Decomposition (link:https://mirror.codeforces.com/blog/entry/44711?#comment-292719)↵

Are there any other interesting ways.↵

Also, what if we have update queries as well. (The above approaches will also work for updates but are there any other ways)↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English C21 2019-08-19 21:55:11 0 (published)
en2 English C21 2019-08-19 21:53:32 23 Tiny change: ' of:\n\n1.Segment tree (li' -> ' of:\n\n1.Using Segment/Merge-Sort tree (li'
en1 English C21 2019-08-19 21:46:32 697 Initial revision (saved to drafts)