Чтобы делать это достаточно эффективно, нужно персистентное декартово дерево. Персистентная структура данных -- это такая, в которой хранятся все предыдущие состояния. При изменении любой вершины она копируется и изменяется только копия, а оригинальная вершина остаётся в прежнем состоянии. Таким образом, копирование -- просто копирование указателя.

Почитать можно, например, тут; наверняка на КФ можно ещё чего-то нарыть.

Если ты такой умный, то почему такой синий?