Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

[Help] Moving down an Iterative Segment Tree

Revision en1, by Lain, 2020-11-06 15:53:43

### 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;
}


Reference submission

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 Lain 2020-11-06 15:53:43 1164 Initial revision (published)