[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.

Tags #segment tree, #lazy propagation, iterative, #help

History

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