persistent seg tree

int arr[MAX];

struct node{
    node *left,*right;
    int sum;
    node(){
        sum = 0;
        left = right = NULL;
    }
}*root[MAX];

node* Build(int b,int e){
    if(b==e){
        node *ret = new node();
        ret->sum = arr[b];
        return ret;
    }
    int mid = (b+e)>>1;
    node *ret = new node();
    ret->left = Build(b,mid);
    ret->right = Build(mid+1,e);
    ret->sum = ret->left->sum + ret->right->sum;
    return ret;
}

node *update(node *ptr,int b,int e,int indx,int val){

    if(b>indx||indx>e)return ptr;
    if(b==e){
        node *ret = new node();
        ret->sum = ptr->sum + val;
        return ret;
    }
    int mid = (b+e)>>1;
    node *ret = new node();
    ret->left = update(ptr->left,b,mid,indx,val);
    ret->right = update(ptr->right,mid+1,e,indx,val);
    ret->sum = ret->left->sum + ret->right->sum;
    return ret;
}


int query(node *ptr,int b,int e,int l,int r){
    if(b>r||l>e)return 0;
    if(b>=l&&e<=r)return ptr->sum;
    int mid = (b+e)>>1;
    return query(ptr->left,b,mid,l,r) + query(ptr->right,mid+1,e,l,r);
}

int main()
{
    booster()
    ///read("input.txt");

    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)cin>>arr[i];
    root[0] = Build(1,n);

    int q;
    cin>>q;
    int ajinka = 1;
    while(q--){
        int ch;
        cin>>ch;
        int idx;
        int a,b;
        cin>>idx>>a>>b;
        if(ch==1){
            root[ajinka] = update(root[idx],1,n,a,b);
            ajinka++;
        }
        else cout<<query(root[idx],1,n,a,b)<<endl;
    }


    return 0;
}