# Is there a iterative lazy propogation algorithm

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?

1 Like

This has iterative lazy propogation ig? Idk

1 Like

If you only want template you can use mine. I had already spent a lot time creating them but tbh i don’t find any significant difference when it comes to Recursive Vs Iterative seg tree. Morever recursive ones are flexible in terms of changes as per question. Link1 Link2 Link3 Link4

1 Like

Define variables globally (just suggestion).I think recursive is easy to understand.

1 Like

Defining variables (i.e node index, left pointer, right pointer etc) globally will be a completely wrong approach and you will end up with a WA. Try drawing recursion calls and you will understand that it traverses only a single path not the complete recursion tree.

Not all variables bro its common sense that we will result in WA we can define lazy array,Core tree for array globally obviously we must have pass limit poiters.