SIGSEGV on Segment Tree for large sized array
Разница между en1 и en2, 200 символ(ов) изменены
After reading some tutorials on segment tree:↵

- [Efficient and easy segment trees](http://codeforces.net/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 &mdash; 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский madhur4127 2017-12-26 18:30:41 200 Tiny change: '! \n\n\n\nUPD: Its solv' -> '! \n\n\n\n**UPD**: Its solv'
en1 Английский madhur4127 2017-12-26 16:37:00 3120 Initial revision (published)