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!