Problem in implementing Persistent Segment Tree

Question

I am trying to implement Persistent Segment Tree. The queries are of 2 types: 1 and 2.

1 ind val : update the value at ind to val in the array

2 k l r : find the sum of elements from index l to r after the kth update operation.

I have implemented the update and query functions properly and they are working fine on an array. But the problem arises when I am forming different versions. Basically this is my part of code

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);

Now the problem is it is also changing the parameters for the all the node is the array. That means after 3 updates all the versions are storing the latest tree. This is probably because I am not properly allocating the new pointer. The changes made to the new pointer are getting reflected in all the pointers in the array

For example if I give this input

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

where 5 is the number of elements in the array and following is the array. Then there is q, number of queries and then all the queries. After carrying out the update the value of query function called for (l, r) = (0, 1) for all the 3 versions are 15. But it should be 3, 11, 15. What am I doing wrong

Answer 1

So let's say we have some simple segment tree like this:

For Persistant segment tree, during update we generate new nodes for all changed nodes and replace pointers to new nodes where needed, so let's say we update node 4, then we get a persistent segment tree like this (new nodes marked with *):

And all you're doing is replacing the root and copying all data so you get something like this: