The Problem
I am trying to solve problem 1136E, where I need to find the lowest $$$pos$$$ such that $$$b_{pos} \geq b_i + x$$$. I generally use the lazy segment tree from the AtCoder Library, which is iterative. In a recursive segment tree, I could just move down the tree choosing the left or right node. How do I do this in an iterative segment tree?
My attempt
int find_pos(int val)
{
int root = 1;
while (root < size)
{
push(root);
int l = 2*root;
int r = 2*root+1;
if (t[l].mx >= val)
root = l;
else
root = r;
}
return root-size;
}
This gives the wrong lower bound on some cases. I think it's because in the iterative case, it is not a clear tree, but rather a set of binary trees. Usually we move bottom up when calculating in an iterative segtree, so either it is not possible in an iterative segtree (without magic) or I have misunderstood something. Please let me know.