Lain's blog

[Help] Moving down an Iterative Segment Tree
By Lain, history, 4 years ago, In English

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.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As far as I know it is still possible to move down the tree in order, but it is very hard since IT-segment-tree is a forest of binary trees. And the implementations might be complex or even unreadable for some specific problems

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Since your implementation pads the size of the iterative segment tree to a power of two and the out-of-bounds region cannot corrupt any of the range maxes you will examine, you effectively have only one complete binary tree and not a forest. It's possible to manage the forest underlying an iterative segment tree with no such padding, and the resulting code more closely resembles the lazy update part of your code or a binary search from an interior point of a recursive segment tree, but that shouldn't be necessary. The idea behind your attempt should more or less 'just work'. The runtime error your submission happens because your found position can be as large as size - 1 (when no large enough element exists), which may be greater than _n, eventually triggering the assertion at the start of lazy_segtree::apply(int, int, F). Happy debugging!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh you're right, I realized the assertion was the issue but not why. Thanks for your help!

    Is there anything you can do with a recursive segtree that is impossible in an iterative one? I'm aware of persistence being an issue and implicit segment tree being annoying, but is there anything else to watch out for?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I once had to do range-add and range-min operations on a segment as fast as possible. This is relatively easy with a segment tree that stores min on subsegment, as well as a bias value that gets added to each element on the subsegment from past queries (with no lazy propagation, because that is slow). I haven't found a good way of doing this on an iterative segment tree.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Isn't Iterative seg with lazy fast enough?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My intuition says that it would be slower in general due to more memory accesses, but I could be wrong. Moreover, in my case I was able to optimize the (recursive) segment tree a lot by doing some branch-and-bound.

          There's definitely other cases where iterative segment tree is just a pain (binary search on range, for example).

          Personally, I think a lot of the benefits of the iterative segment tree can be achieved (without giving away versatility) by switching the bfs-order node labelling strategy to a dfs-order one in a recursive segment tree. This achieves $$$2N-1$$$ nodes for $$$N$$$ leaves, and also has better cache locality.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            This comment suggests that iterative segtree is much faster, but I haven't looked into it myself. However like you said, a lot of things become odd and non-trivial in the case of iterative segment trees.

            About your initial comment, what do you mean by adding a bias value to each element on the subsegment? I'm not sure how it could be faster than lazy propagation.

            → Reply