I’m trying to make lazy segment tree, but all the resources I’ve found are recursive.
The codes look absolutely horrendous, by passing 6 variables every recursion. For normal segment tree there’s a beautiful iterative approach, which looks much better
My Segment Tree
template<typename T>
struct segment_tree{
vector<T> segtree;
int n;
T (*join)(T,T);
segment_tree(vector<T> &a, int size, T (*merge)(T,T)){
n=size;
join=merge;
segtree.resize(2*n);
for(int i=0;i<n;i++){
segtree[n+i]=a[i];
}
for(int i=n-1;i>=1;i--){
segtree[i]=join(segtree[2*i], segtree[2*i + 1]);
}
}
void update(int pos, T val){
pos+=n;
segtree[pos]=val;
pos>>=1;
while(pos){
segtree[pos]=join(segtree[2*pos],segtree[2*pos+1]);
pos>>=1;
}
}
T query(int x, int y){
T ans;
x+=n;
y+=n+1;
while(x<y){
if(x&1){
ans=join(ans,segtree[x++]);
}
if(y&1){
ans=join(ans,segtree[--y]);
}
x>>=1;
y>>=1;
}
return ans;
}
};
Is it even possible to use a bottom-up lazy propogation?