having an array $$$arr$$$ with $$$n$$$ elements we have two types of queries:
- given an index $$$idx$$$ and a value $$$val$$$, $$$arr_{idx}:=val$$$
- 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.
Check out Segment Trees
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.
Auto comment: topic has been updated by Jus_here_to_learn_dude (previous revision, new revision, compare).
We can use 3D MO — $$$O(n ^ {5/3})$$$.
There is also a solution $$$O(n log ^ 2 n)$$$.
If there are no change requests, then the wavelet tree in $$$O(n log n)$$$ can be used.
can you provide more info or some reference for the second solution?
I don't know the algorithm, but I know it exists.
In this blog you can find the same question
This might be helpful (it uses persistent segment trees which is an advanced topic)
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.