Is it possible to make data structure that will find MEX and support modification queries

Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX (Minimum EXcluded) meaning the smallest positive integer that is not present in the set. More info from wikipedia. The data structure should also support insert and remove elements from itself.

In other words, we have given a multiset with $n$ elements, we want to find its MEX, but we should support removing and adding elements.

What I was thinking was that we should first process the elements on some way, and then when adding new element in the set we should check if it is equal to the MEX, but there are many cases to worry about, so I couldn't come to complete solution.

The data structure should support both the queries/updates in $O(\log N)$ or similar time-complexity classes.

Method 1

You can also use a bit trie — this is a trie made of bits of your numbers, thus it is represented as a binary tree (since there are only two types of bits — 0 and 1), and its depth is $\mathcal{O}{(log(n))}$.

When you add a number, you mark the vertex that representing this particular number as a full binary tree, and then you recursively go over its parents marking them as full binary trees if their left and right children are both full binary trees as well.

When you remove a number, you unset the "full binary tree" mark and do so for all its parents.

When you want to get MEX, you should do the DFS towards $x$, avoiding visiting subtrees which are marked as full (because there are no free values in such subtrees) and attempt to visit a left subtree first if you are allowed to by the x restriction.
class MEX {
struct MEXNode {
MEXNode *children[2];
bool is_full = false;
int cnt = 0;

public:
MEXNode() {
children[0] = nullptr;
children[1] = nullptr;
}
};
private:

inline MEXNode nonnull(MEXNode & n) {
if (!n) n = new MEXNode();
return n;
}

void insert(int val, int level, MEXNode *n) {
if (level == -1) {
n->cnt++;
n->is_full = true;
return;
}

int cur_bit = (val & (1 > level;
insert(val, level - 1, nonnull(n->children[cur_bit]));

n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
}

// Remove an integer from the set
void remove(int val, int level, MEXNode *n) {
if (level == -1) {
n->cnt--;
n->is_full = n->cnt > 0;
return;
}

int cur_bit = (val & (1 > level;
remove(val, level - 1, nonnull(n->children[cur_bit]));

n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
}

// Find the minimum element >=x that isn't present in the set
int get(int val, int level, MEXNode *n) {
if (n->is_full) {
return -1;
} else if (n->cnt == 0) {
return val;
}

int cur_bit = (val & (1 > level;
int ans = get(val, level - 1, nonnull(n->children[cur_bit]));
if (cur_bit == 0 && ans == -1) {
ans = get((val >> level children[1]));
}

return ans;
}

MEXNode root_node;
public:

void insert(int x) {
insert(x, 31, &root_node);
}
void remove(int x) {
remove(x, 31, &root_node);
}
int get(int x) {
return get(x, 31, &root_node);
}
};


Method 2

Create a set of intervals $S$. If the interval $[l, r]$ is present in $S$, that means that the elements $l, l + 1, l + 2, \dots , r$ are in $S$.

Adding an element $x$ is handled like this:
If $[whatever, x - 1]$ is present in the set, remove it and add $[whatever, x]$. Likewise, if $[x + 1, whatever]$ is in the set, remove it and add $[x, whatever]$.

Removals are handled in this way:
Find the interval containing x. Split it into two intervals $[start, x - 1]$, and $[x + 1, end]$.

MEX queries are handled similarly:
Find the interval containing $x$ and output $end + 1$. This can be implemented using 2 std::set in C++.

The first set indexes pairs by the first element (i.e. left end), and the second one by their second element (i.e. right end)
`class MEX {
typedef std::pair interval;
std::set s[2];
std::multiset values;
void insert_pair(interval p) {
auto[x, y] = p;
if (x > y) std::swap(x, y);
s[0].insert({x, y});
s[1].insert({y, x});
}
void remove_pair(interval p) {
auto[x, y] = p;
if (x > y) std::swap(x, y);
s[0].erase({x, y});
s[1].erase({y, x});
}

std::optional is_end(int x, bool left) {
int idx = left;
auto it = s[idx].lower_bound({x, 0});
if (it != s[idx].end() && it->first == x)
return *it;
else
return std::nullopt;
}

public:
void insert(int x) {
bool ok = values.find(x) == values.end();
values.insert(x);
if (!ok) return;
auto p1 = is_end(x - 1, true);
auto p2 = is_end(x + 1, false);
if (p1 && p2) {
interval i = {p1->second, p2->second};
remove_pair(*p1);
remove_pair(*p2);
insert_pair(i);
} else if (p1 && !p2) {
interval i = {p1->second, x};
remove_pair(*p1);
insert_pair(i);
} else if (!p1 && p2) {
interval i = {x, p2->second};
remove_pair(*p2);
insert_pair(i);
} else if (!p1 && !p2) {
interval i = {x, x};
insert_pair(i);
}
}
void remove(int x) {
values.erase(values.find(x));
if (values.find(x) != values.end()) return;
auto it = s[1].lower_bound({x, 0});
if (it->first != x && it->second != x) {
interval p1 = {it->second, x - 1};
interval p2 = {x + 1, it->first};
remove_pair(*it);
insert_pair(p1);
insert_pair(p2);
} else if (it->first != x && it->second == x) {
interval

StackExchange Computer Science Q#88528, answer score: 3