After reading some tutorials on segment tree:↵
↵
- [Efficient and easy segment trees](http://mirror.codeforces.com/blog/entry/18051) ↵
↵
- [Segment Tree by e-maxx](http://e-maxx.ru/algo/segment_tree) ↵
↵
↵
I thought to implement this data structure in Object Oriented methodology whereby I used vector instead of arrays in (contrast with tutorials) approach to hide implementation details, but it verdicts SIGSEGV for size in order of 10^5. But works fine (I hope) for array size less than of 10^4 order;↵
↵
↵
~~~~~↵
typedef struct SegmentTree{↵
vector<int> tree, udp; int orgsize;↵
/******************BUILD***********************/↵
SegmentTree(vector<int>& list){ //CONSTRUCTOR↵
orgsize=list.size();↵
int size=((int)(pow(2,31-__builtin_clz(orgsize))))<<1;↵
tree.resize(size); udp.assign(size,0); build(1,0,orgsize-1,list);↵
}↵
void build(int cur, int s, int e, vector<int>& list){↵
if(s==e){ tree[cur]=list[s]; return ;}↵
else{↵
int mid=(s+e)/2;↵
build(cur<<1,s,mid,list); build((cur<<1)+1,mid+1,e,list);↵
tree[cur]= tree[cur<<1]+tree[(cur<<1)+1]; //NODE FUNCTION↵
}↵
}↵
/*************** UPDATE **************************/↵
void update(int s, int e, int val){ update(1,0,orgsize-1,s,e,val);}↵
void update(int cur, int ts, int te, int s, int e, int val){ //ts: temporary start, cur: current↵
if(ts>=s && te<=e) udp[cur]+=val;↵
else{↵
tree[cur]+=(min(te,e)-max(ts,s)+1)*val; //NODE FUNCTION↵
int mid=(ts+te)/2;↵
if(mid>=s && ts<=e) update(cur<<1,ts,mid,s,e,val);↵
if(mid+1<=e && te>=s) update((cur<<1)+1,mid+1,te,s,e,val);↵
}↵
}↵
/*************** QUERY ***************************/↵
ll query(int s, int e){return q(1,0,orgsize-1,s,e);}↵
ll q(int cur, int ts,int te, int s, int e){ //ts: temporary start, cur: current↵
if(ts>=s && te<=e){↵
if(udp[cur]!=0){↵
tree[cur]+=(te-ts+1)*udp[cur]; //NODE FUNCTION↵
if(2*cur < udp.size()){↵
udp[cur<<1]+=udp[cur];↵
udp[(cur<<1)+1]+=udp[cur];↵
}↵
udp[cur]=0;↵
}↵
return tree[cur];↵
}↵
else{↵
tree[cur]+=(te-ts+1)*udp[cur];↵
if((cur<<1) < udp.size()){↵
udp[cur<<1]+=udp[cur];↵
udp[(cur<<1)+1]+=udp[cur];↵
}↵
udp[cur]=0;↵
ll temp=0; int mid=(ts+te)/2;↵
if(mid>=s && ts<=e) temp+=q(cur<<1,ts,mid,s,e);↵
if(mid+1<=e && te>=s) temp+=q((cur<<1)+1,mid+1,te,s,e);↵
return temp;↵
}↵
}↵
} ST;↵
~~~~~↵
↵
↵
I tried this program for [SPOJ-Horrible](http://www.spoj.com/problems/HORRIBLE/) and get "Runtime error — SIGSEGV" which then I presume to arise from implementation as when I tried running on 10^5 it shows that error again.↵
↵
My submission for above mention problem: [Ideone](https://ideone.com/1bfAaO)↵
↵
I tried using global vector of the object udp & tree and also the vector which I used to build this segment tree. But it didn't work. Is there a fix or shall I not use this OOP based implementation? Because ↵
↵
Thank you for having time to read this.! ↵
↵
↵
↵
**UPD**: Its solved! For those who are wondering the source of bug, it was in the calculation of size in constructor changing to `2 << (32 - __builtin_clz(orgsize - 1))` led to Accepted verdict.
↵
- [Efficient and easy segment trees](http://mirror.codeforces.com/blog/entry/18051) ↵
↵
- [Segment Tree by e-maxx](http://e-maxx.ru/algo/segment_tree) ↵
↵
↵
I thought to implement this data structure in Object Oriented methodology whereby I used vector instead of arrays in (contrast with tutorials) approach to hide implementation details, but it verdicts SIGSEGV for size in order of 10^5. But works fine (I hope) for array size less than of 10^4 order;↵
↵
↵
~~~~~↵
typedef struct SegmentTree{↵
vector<int> tree, udp; int orgsize;↵
/******************BUILD***********************/↵
SegmentTree(vector<int>& list){ //CONSTRUCTOR↵
orgsize=list.size();↵
int size=((int)(pow(2,31-__builtin_clz(orgsize))))<<1;↵
tree.resize(size); udp.assign(size,0); build(1,0,orgsize-1,list);↵
}↵
void build(int cur, int s, int e, vector<int>& list){↵
if(s==e){ tree[cur]=list[s]; return ;}↵
else{↵
int mid=(s+e)/2;↵
build(cur<<1,s,mid,list); build((cur<<1)+1,mid+1,e,list);↵
tree[cur]= tree[cur<<1]+tree[(cur<<1)+1]; //NODE FUNCTION↵
}↵
}↵
/*************** UPDATE **************************/↵
void update(int s, int e, int val){ update(1,0,orgsize-1,s,e,val);}↵
void update(int cur, int ts, int te, int s, int e, int val){ //ts: temporary start, cur: current↵
if(ts>=s && te<=e) udp[cur]+=val;↵
else{↵
tree[cur]+=(min(te,e)-max(ts,s)+1)*val; //NODE FUNCTION↵
int mid=(ts+te)/2;↵
if(mid>=s && ts<=e) update(cur<<1,ts,mid,s,e,val);↵
if(mid+1<=e && te>=s) update((cur<<1)+1,mid+1,te,s,e,val);↵
}↵
}↵
/*************** QUERY ***************************/↵
ll query(int s, int e){return q(1,0,orgsize-1,s,e);}↵
ll q(int cur, int ts,int te, int s, int e){ //ts: temporary start, cur: current↵
if(ts>=s && te<=e){↵
if(udp[cur]!=0){↵
tree[cur]+=(te-ts+1)*udp[cur]; //NODE FUNCTION↵
if(2*cur < udp.size()){↵
udp[cur<<1]+=udp[cur];↵
udp[(cur<<1)+1]+=udp[cur];↵
}↵
udp[cur]=0;↵
}↵
return tree[cur];↵
}↵
else{↵
tree[cur]+=(te-ts+1)*udp[cur];↵
if((cur<<1) < udp.size()){↵
udp[cur<<1]+=udp[cur];↵
udp[(cur<<1)+1]+=udp[cur];↵
}↵
udp[cur]=0;↵
ll temp=0; int mid=(ts+te)/2;↵
if(mid>=s && ts<=e) temp+=q(cur<<1,ts,mid,s,e);↵
if(mid+1<=e && te>=s) temp+=q((cur<<1)+1,mid+1,te,s,e);↵
return temp;↵
}↵
}↵
} ST;↵
~~~~~↵
↵
↵
I tried this program for [SPOJ-Horrible](http://www.spoj.com/problems/HORRIBLE/) and get "Runtime error — SIGSEGV" which then I presume to arise from implementation as when I tried running on 10^5 it shows that error again.↵
↵
My submission for above mention problem: [Ideone](https://ideone.com/1bfAaO)↵
↵
I tried using global vector of the object udp & tree and also the vector which I used to build this segment tree. But it didn't work. Is there a fix or shall I not use this OOP based implementation? Because ↵
↵
Thank you for having time to read this.! ↵
↵
↵
↵
**UPD**: Its solved! For those who are wondering the source of bug, it was in the calculation of size in constructor changing to `2 << (32 - __builtin_clz(orgsize - 1))` led to Accepted verdict.
