SegTree, C++ (gcc)

SegTree

class SegTree
{
   public:
     int n;
   int *seg= new int[4*n];

const int NA=0;

SegTree(const int n):n(n)
    {}
   
    int func(const int a,const int b)const{return a+b;}
   int build(const int a[]){for(int i=0;i<4*n;i++)seg[i]=0;return build1(a,0,n-1,1);}
   int build1(const int a[],int ss,int se,int cur)
    {
       if(ss==se)return seg[cur]=a[ss];      
       int mid=(ss+se)/2;
       return seg[cur]= func(build1(a,ss,mid,2*cur),build1(a,mid+1,se,2*cur+1));

}
    int subquery(int qs,int qe,int ss,int se,int cur)const
    {
      if(qs>se || qe<ss)return NA;
      if(ss>=qs && se<=qe)return seg[cur];
      int mid=(ss+se)/2;
      return func(subquery(qs,qe,ss,mid,2*cur),subquery(qs,qe,mid+1,se,2*cur+1));
    }
    int query(int qs,int qe)const
    {
       return subquery(qs,qe,0,n-1,1);
    }
     
    void update(const int ind,const int val)
    {
       int ss=0,se=n-1,cur=1;
       while(ss!=se){int mid=(ss+se)/2;if(mid<ind){ss=mid+1;cur=2*cur+1;}else{se=mid;cur=2*cur;}}
       seg[cur]=val;cur/=2;
       while(cur>0){seg[cur]=func(seg[2*cur],seg[2*cur+1]);cur/=2;}
    } 
    void print()const{for(int i=0;i<4*n;i++)cout<<seg[i]<<" ";cout<<'\n';}
};


run \| edit \| history \| help	-1

λ

                                      .NET NoSQL database for rapid development