Проблема реализации персистентного дерева сегментов

Question

Я пытаюсь реализовать дерево постоянных сегментов. Запросы бывают двух типов: 1 и 2.

1 ind val: обновить значение массива ind до val в массиве

2 k l r: найти сумму элементов от индекса l до r после k-й операции обновления.

Я правильно реализовал функции обновления и запроса, и они отлично работают в массиве. Но проблема возникает, когда я формирую разные версии. В основном это моя часть кода

while (q--) {
        cin >> type;
        if (type == 1) {
            cin >> ind >> val;

            node *t = new node;
            *t = *ver[size - 1];
            update(t, ind, val);
            ver.pb(t);
            size++;

        }

    }

cout << query(ver[0], 0, 1) << ' ' << query(ver[1], 0, 1) << query(ver[2], 0, 1);

Теперь проблема в том, что он также изменяет параметры для всех узлов массива. Это означает, что после 3 обновлений все версии хранят последнее дерево. Вероятно, это связано с тем, что я неправильно распределяю новый указатель. Изменения, внесенные в новый указатель, отражаются во всех указателях в массиве

Например, если я введу это значение

5
1 2 3 4 5
2
1 1 10
1 0 5

где 5 - количество элементов в массиве, а следующее - массив. Тогда есть q, количество запросов, а затем все запросы. После выполнения обновления значение запрашиваемой функции запроса (l, r) = (0, 1) для всех 3 версий равно 15. Но должно быть 3, 11, 15. Что я делаю не так

Answer 1

Допустим, у нас есть простое дерево сегментов, подобное этому:

Для дерева сегментов Persistant во время обновления мы генерируем новые узлы для всех измененных узлов и заменяем указатели на новые узлы там, где это необходимо, поэтому, скажем, мы обновляем узел 4, затем мы получаем постоянное дерево сегментов, подобное этому (новые узлы отмечены * ):

И все, что вы делаете, это заменяете корень и копируете все данные, чтобы вы получили что-то вроде этого: