C21's blog

Different Approaches to query: number of distinct elements from [L,R]
By C21, history, 5 years ago, In English

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)

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by C21 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

703D - Mishka and Interesting sum

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But this is an offline approach.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use a persistent segment tree in a very similar fashion to your first link.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply