Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
TempSpecial
div
pow implementation
Guess Number
arthi3.cpp
NameTempSpecial
st_match
1234
SIP_parser_with_std_regex_need_help_to_improve_it.cc
std::erf versus erf_impl (Abramowitz & Stegun)