TOPIC

Why I get RTE

Boyiddha_ asked 3 years ago

I apply Persistent Segment Tree..... Why this code get Run Time Error

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mx 100007

struct node{
    ll val;
    node *left,*right;
    node(node *l,node *r,ll v){
        left=l;
        right=r;
        val=v;
    }
};
ll arr[mx];
node *version[mx];

void buildTree(node *root,int l,int r){
    if(l==r)root->val=arr[l];
    else{
        int mid=(l+r)/2;
        root->left=new node(NULL,NULL,0);
        root->right=new node(NULL,NULL,0);
        buildTree(root->left,l,mid);
        buildTree(root->right,mid+1,r);
        root->val=root->left->val+root->right->val;
    }
}
void update(node *prev,node *curr,int l,int r,int indx,int value){
    if(l>r||indx<l||r<indx)return;
    if(l==r){
        curr->val=value;
        return;
    }
    int mid=(l+r)/2;
    if(indx<=mid){
        curr->right=prev->right;
        curr->left=new node(NULL,NULL,0);
        update(prev->left,curr->left,l,mid,indx,value);
    }
    else{
        curr->left=prev->left;
        curr->right=new node(NULL,NULL,0);
        update(prev->right,curr->right,mid+1,r,indx,value);
    }
    curr->val=curr->left->val+curr->right->val;
}
ll query(node *root,int l,int r,int x,int y){
    if(l>r||r<x||l>y)return 0;
    if(l>=x&&r<=y)return root->val;
    int mid=(l+r)/2;
    ll a=query(root->left,l,mid,x,y);
    ll b=query(root->right,mid+1,r,x,y);
    return a+b;
}

int main(){
    int n,q,check,x,y,k,w,updt;
    while(cin>>n &&n){
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        node *root=new node(NULL,NULL,0);
        buildTree(root,0,n-1);
        version[0]=root;
        cin>>q;
        updt=0;
        while(q--){
            cin>>check;
            if(check==1){
                cin>>x>>y>>k;
                cout<<query(version[k],0,n-1,x-1,y-1)<<endl;
            }
            else if(check==2){
                cin>>x>>w;
                int vrsn=updt;
                version[vrsn+1]=new node(NULL,NULL,0);
                update(version[vrsn],version[vrsn+1],0,n-1,x-1,w);
                updt++;
            }
        }
    }

    return 0;
}

This topic has not been answered yet. Be the first!

Remember not post solutions. Your post may be reviewed by our moderators.