Jus_here_to_learn_dude's blog

range MEX queries with updates
By Jus_here_to_learn_dude, 2 weeks ago, In English

having an array $$$arr$$$ with $$$n$$$ elements we have two types of queries:

  1. given an index $$$idx$$$ and a value $$$val$$$, $$$arr_{idx}:=val$$$
  2. given a range $$$(l,r)$$$, find the $$$MEX$$$ of the range

what is the most efficient way to do this?

i'd be grateful if you could share some c++ code to do this.

thanks in advance guys.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Check out Segment Trees

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

    I know seg trees and square root decomposition are possible options, but i'm not quite sure how to actually implement it. thanks for the reply anyways.

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

We can use 3D MO — $$$O(n ^ {5/3})$$$.

There is also a solution $$$O(n log ^ 2 n)$$$.

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

    If there are no change requests, then the wavelet tree in $$$O(n log n)$$$ can be used.

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

    can you provide more info or some reference for the second solution?

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This might be helpful (it uses persistent segment trees which is an advanced topic)

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

    thanks man. I knew about MO's but had never heard of 3D MO or persistent seg trees. interesting! I'll spend some time studying these.

    → Reply