madhur4127's blog

SIGSEGV on Segment Tree for large sized array
By madhur4127, history, 7 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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;. Although pow(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 like 2 << (32 - __builtin_clz(orgsize - 1)) or a simple while loop which would calculate tree size.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        There should not be any problems with double precision there: powers of two are always stored precisely.

        → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Try removing int arr[n]; from main and use a vector instead. You're overflowing the stack.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by madhur4127 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

My first thought was "do not use standard pow because it's imprecise". My second thought was "wait, but double stores 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 pow from math.h works by combining log and exp, 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 as pow(int, int), so a templated overload from std is 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;

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, but 2 << (32 - __builtin_clz(orgsize - 1)) worked well and got AC'ed

    Learned a lot from this discussion!

    → Reply