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.net/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)
Auto comment: topic has been updated by C21 (previous revision, new revision, compare).
703D - Mishka and Interesting sum
But this is an offline approach.
You can use a persistent segment tree in a very similar fashion to your first link.
This is a Online Approach to the problem in O((N+Q)*logN) using persistent segment tree.
However, this doesn't work with updates as far as i know.