实现持久线段树的问题

Question

我正在尝试实现持久线段树。查询有两种类型：1 和 2。

1 ind val : 将 ind 处的值更新为数组中的 val

2 k l r ：求第k次更新操作后从索引l到r的元素之和。

我已经正确实现了更新和查询功能，它们在数组上运行良好。但是当我形成不同的版本时，问题就出现了。基本上这是我的代码部分

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 是数组中元素的数量，后面是数组。然后是 q，查询数，然后是所有查询。执行更新后，所有 3 个版本的 (l, r) = (0, 1) 查询函数的值都是 15。但它应该是 3、11、15。我做错了什么

Answer 1

假设我们有一些像这样的简单线段树：

对于永久线段树，在更新期间我们为所有更改的节点生成新节点并在需要时替换指向新节点的指针，所以假设我们更新节点 4，然后我们得到一个像这样的永久线段树（新节点标记为带 *):

你所做的只是替换根目录并复制所有数据，这样你就会得到如下内容：

实现持久线段树的问题

Problem in implementing Persistent Segment Tree

persistent

segment-tree