Different Approaches to query: number of distinct elements from [L,R]

Revision en2, by C21, 2019-08-19 21:53:32

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)

Tags #segment tree, #sqrt decomposition, #range query

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)