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://codeforces.me/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)↵
↵
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://codeforces.me/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)↵
