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