After reading some tutorials on 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 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
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.
Do you have a test on which that implementation fails?
This line makes me extremely uncomfortable:
int size=((int)(pow(2,31-__builtin_clz(orgsize))))<<1;. Althoughpow(2, ...)should yield a precise result, I prefer to avoid involving floating point arithmetic unless I really have to, so I'd replace that with something like2 << (32 - __builtin_clz(orgsize - 1))or a simplewhileloop which would calculate tree size.It seems you pointed bug correctly I changed to
2 << (32 - __builtin_clz(orgsize - 1))and it worked, but still I wonder why downcast failed.I also tried printing
(int)pow(10,5) and (int)(1e5)but it was correct.Anyways, now it works, thanks again!
downcast may fail because the double can't store the number, because double precision is weird, like the smallest difference between 2 large doubles could be like 10000.
There should not be any problems with double precision there: powers of two are always stored precisely.
Try removing
int arr[n];from main and use a vector instead. You're overflowing the stack.thank you for help, as yeputons pointed the mistake was there in my pow function.
Auto comment: topic has been updated by madhur4127 (previous revision, new revision, compare).
My first thought was "do not use standard
powbecause it's imprecise". My second thought was "wait, butdoublestores numbers internally as a·2b, which means that power of two can be stored precisely".Bad news 1: even though it's possible to store result precisely, it's quite probably that
powfrommath.hworks by combininglogandexp, which introduces some imprecision.Bad news 2: even though there is a manually implemented
pow(double, int)in the code, it's not called since C++11 unless we call it with exactly that set of arguments. However, in the constructor it's called aspow(int, int), so a templated overload fromstdis called instead (see no. 7). Which can introduce some imprecision.So here is another workaround which may or may not work:
int size=((int)(pow(2.0,31-__builtin_clz(orgsize))))<<1;bad news :(: It didn't work, it called my pow function, instead of overloaded from library.
Using
int size=((int)(pow(2.0,31-__builtin_clz(orgsize))))<<1;gave RTE again, but2 << (32 - __builtin_clz(orgsize - 1))worked well and got AC'edLearned a lot from this discussion!