可持久化线段树，8pts，样例有一个询问没过，最后有很多WA（当然还有几个TLE）https://www.luogu.com.cn/record/198690927 这是我的代码，求各位大神修改，玄关

#include <cstdio>
#include <vector>
#define uint unsigned long long
#define sint long long
struct node{
    sint val;
    node* leftChild;
    node* rightChild;
    node(){
        leftChild = rightChild = nullptr;
        val = 0;
    }
};
const int maxn = (1 << 20) + 5;
int arr[maxn];
int maxLevel = 20;

std::vector <node*> root;
void build(int level = 0, int pos = 0, node* rt = root[0]){
    if(level == maxLevel){
        rt -> val = arr[pos];
        return;
    }
    rt -> leftChild = new node();
    build(level + 1, pos << 1, rt -> leftChild);
    rt -> rightChild = new node();
    build(level + 1, pos << 1 | 1, rt -> rightChild);
    rt -> val = rt -> leftChild -> val + rt -> rightChild -> val;
}
void update(int id, int pos, int val){
    node* pre = root[id];
    node* newRoot = new node();
    root.push_back(newRoot);
    std::vector <node*> path;
    path.push_back(newRoot);
    for(int i = maxLevel; i > 0; i--){
        if(pos & (1 << i)){
            newRoot -> leftChild = pre -> leftChild;
            newRoot -> rightChild = new node();
            pre = pre -> rightChild; 
            newRoot = newRoot -> rightChild;
            path.push_back(newRoot);
        } 
        else{
            newRoot -> rightChild = pre -> rightChild;
            newRoot -> leftChild = new node();
            pre = pre -> leftChild;  
            newRoot = newRoot -> leftChild;
            path.push_back(newRoot);
        }
    }
    path.back() -> val = val;
    path.pop_back();
    while(path.size()){
        path.back() -> val = path.back() -> leftChild -> val + path.back() -> rightChild -> val;
        path.pop_back();
    }
}
int query(int id, int pos){
    node* pre = root[id];
    node* newRoot = new node();
    newRoot -> val = pre -> val;
    root.push_back(newRoot);
    for(int i = maxLevel - 1; i >= 0; i--){
        if(pos & (1 << i)){
            if(pre -> leftChild) newRoot -> leftChild = pre -> leftChild;
            newRoot -> rightChild = new node();
            pre = pre -> rightChild; 
            newRoot = newRoot -> rightChild;
            newRoot -> val = pre -> val;
        } 
        else{
            if(pre -> rightChild) newRoot -> rightChild = pre -> rightChild;
            newRoot -> leftChild = new node();
            pre = pre -> leftChild;  
            newRoot = newRoot -> leftChild;
            newRoot -> val = pre -> val;
        }
    }
    return pre -> val;
}
int main()
{
    root.push_back(new node());
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &arr[i]);
    }
    build();
    for(int i = 0; i < m; i++){
        int id, op;
        scanf("%d %d", &id, &op);
        if(op == 1){
            int pos, val;
            scanf("%d %d", &pos, &val);
            update(id, pos, val);
        }
        if(op == 2){
            int pos;
            scanf("%d", &pos);
            printf("%d\n", query(id, pos));
        }
    }
    return 0;
}

谢谢！