Jus_here_to_learn_dude's blog

range MEX queries with updates
By Jus_here_to_learn_dude, 17 months 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

Comments Comments (9)
| Write comment?
»
17 months ago, hide # |
← 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
»
17 months ago, hide # |
 
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
»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For range MEX with point updates, I believe the best known solution is $$$\mathcal{O}(\log^3{n})$$$ per operation. Key observations:

  1. $$$\text{MEX} \geq k$$$ iff exactly $$$k$$$ distinct values from $$$[0,k)$$$ appear in the range
  2. values $$$ \gt n$$$ can be treated as $$$n$$$.

Using a wavelet tree with value as the top-level dimension, we avoid an extra log factor from binary searching on value.

Let me know if you'd like a wavelet tree blog (it would explain my solution in more detail). It's my favorite data structure and I think it deserves better coverage.

→ Reply