Thunder8971's blog

By Thunder8971, 18 months ago, In English

Hello, Codeforces!

Back in 2023, I spent almost an entire week trying to understand how to implement an iterative segment tree with lazy propagation. I had seen implementations before, but some parts felt almost like magic. I could understand what the code was doing, yet I couldn't always explain why it worked or how I would have discovered those operations myself.

Eventually, I decided to approach the problem from scratch, reasoning about the tree, its nodes, and the information each operation needed. That experience led me to write my original tutorial on iterative segment trees.

Looking back, there was something I hadn't fully explored: many of the operations I was performing could be simplified by understanding which parts of the tree actually need to change.

In this blog, I want to revisit that idea. Rather than presenting another template to memorize, I'd like to show how we can derive an iterative lazy segment tree from a few properties, and then use those same properties to solve something beyond ordinary range queries.

We'll use two familiar operations:

  1. Add a value $$$v$$$ to every element in a range.
  2. Find the minimum value in a range.

Both will take $$$O(\log N)$$$ time. Later, we'll extend the same structure to find the first position satisfying a condition, also in $$$O(\log N)$$$.

What does a node actually store?

Let's start with an array $$$A$$$ of length $$$N$$$.

As usual, we round its capacity up to the smallest power of two greater than or equal to $$$N$$$. Let's call this capacity $$$n$$$. The original elements occupy the leaves starting at index $$$n$$$, while each internal node $$$p$$$ has children $$$2p$$$ and $$$2p+1$$$.

We will use zero-based indexing and half-open intervals $$$[l,r)$$$ throughout the implementation. This makes the boundary operations easier to express.

If we only needed range minimum queries, each internal node would satisfy:

$$$ st[p]=\min(st[2p],st[2p+1]). $$$

That part is straightforward. The interesting question appears when we add lazy propagation.

Suppose we add $$$v$$$ to every element represented by some node $$$p$$$. We don't want to visit all its descendants, so we store the update at $$$p$$$ and postpone applying it to its children.

But what should $$$st[p]$$$ represent while that update is pending?

For range addition and minimum queries, we have a useful property:

$$$ \min(a_1+v,\ldots,a_k+v) = \min(a_1,\ldots,a_k)+v. $$$

So we can immediately update the minimum stored at $$$p$$$, while remembering that its children still need to receive $$$v$$$.

This gives us the invariant:

$$$ \boxed{st[p]=\min(st[2p],st[2p+1])+lazy[p]} $$$

for every internal node.

Here, $$$lazy[p]$$$ represents an addition already reflected in $$$st[p]$$$, but not yet propagated to its children. A node's stored minimum may still exclude pending updates from its strict ancestors, so those updates must be pushed before we inspect it independently.

This distinction is important. It means a pending update doesn't make the node's own aggregate incorrect. Its aggregate is already updated; only the information in its descendants is waiting.

From that invariant, three operations follow naturally:

  • apply(p, v) updates the aggregate at $$$p$$$ and records the pending update.
  • push(p) transfers that pending update to both children.
  • pull(p) reconstructs the aggregate at $$$p$$$ from its children while respecting its own pending update.

Notice that pull must include lazy[p]. If we simply replaced $$$st[p]$$$ with the minimum of its children, we could accidentally discard an update that had been applied to the parent but not yet propagated.

Once these rules are clear, lazy propagation becomes less about remembering a sequence of instructions and more about preserving a relationship between the nodes.

Why do only two paths matter?

Now comes my favorite observation.

Suppose we want to process an interval $$$[l,r)$$$. An ordinary iterative segment tree decomposes this interval into a small collection of disjoint nodes, each representing a segment completely contained in our query.

For example, with eight elements, the interval $$$[2,7)$$$ can be represented by:

$$$ [2,4),\quad [4,6),\quad [6,7). $$$

We don't need to visit every element individually. We only need those three nodes.

A straightforward lazy implementation might propagate pending updates from the root to each selected node separately. That works as an initial idea, but there are $$$O(\log N)$$$ selected nodes, and each propagation can cost $$$O(\log N)$$$.

We end up with $$$O(\log^2 N)$$$ work.

But look at what happens if we consider the boundaries of the interval.

Every selected node is completely contained in $$$[l,r)$$$. Furthermore, because the decomposition uses maximal complete segments, its parent cannot be completely contained in the interval.

In other words, every strict ancestor of a selected node that matters for propagation must partially overlap the requested interval.

And here is the key property:

If a node's segment partially overlaps a contiguous interval, that segment must contain at least one of the interval's two boundary elements.

Therefore, all ancestors that we need to prepare are contained in the union of two root-to-leaf paths: the paths to $$$l$$$ and $$$r-1$$$.

Instead of propagating updates separately for every selected node, we can propagate along those two paths first.

After that, the usual iterative interval decomposition can safely read the aggregates of its selected nodes.

The same idea works when updating a range.

We propagate along the two boundary paths, apply the update to the selected nodes, and then reconstruct the necessary ancestors along those same paths.

The important detail is that nodes completely covered by the update can keep their lazy tags. We don't need to rebuild their entire subtrees, and our pull invariant ensures that reconstructing an ancestor doesn't erase those pending updates.

Both paths have length $$$O(\log N)$$$, and the interval decomposition contains $$$O(\log N)$$$ nodes. Therefore:

$$$ T(N)=O(\log N)+O(\log N)+O(\log N) =\boxed{O(\log N)}. $$$

What I like about this observation is that we don't need a special trick for every node. We only need to understand which ancestors may contain information that affects the interval.

Putting everything together

Now let's implement everything.

We'll use st for the minimum values and lazy for pending additions. The functions pushPath and pullPath do exactly what we discussed: propagate information toward a boundary and reconstruct aggregates on the way back.

All ranges use $$$[l,r)$$$, and queries assume $$$0 \le l \lt r \le N$$$.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 60);

struct SegTree {
    int n, h;
    vector<ll> st, lazy;

    SegTree(vector<ll> a) {
        int m = a.size();
        n = 1;
        h = 0;

        while (n < m) {
            n *= 2;
            h++;
        }

        st.assign(2 * n, INF);
        lazy.assign(n, 0);

        for (int i = 0; i < m; i++)
            st[n + i] = a[i];

        for (int i = n - 1; i > 0; i--)
            pull(i);
    }

    void pull(int p) {
        st[p] = min(st[2 * p], st[2 * p + 1])
                + lazy[p];
    }

    void apply(int p, ll v) {
        st[p] += v;
        if (p < n) lazy[p] += v;
    }

    void push(int p) {
        if (lazy[p] == 0) return;

        apply(2 * p, lazy[p]);
        apply(2 * p + 1, lazy[p]);
        lazy[p] = 0;
    }

    void pushPath(int p) {
        for (int s = h; s > 0; s--)
            push(p >> s);
    }

    void pullPath(int p) {
        for (p /= 2; p > 0; p /= 2)
            pull(p);
    }

    // Add v to [l, r).
    void add(int l, int r, ll v) {
        if (l == r) return;

        int L = l + n;
        int R = r + n - 1;

        pushPath(L);
        pushPath(R);

        for (l += n, r += n; l < r;
             l /= 2, r /= 2) {

            if (l & 1) apply(l++, v);
            if (r & 1) apply(--r, v);
        }

        pullPath(L);
        pullPath(R);
    }

    // Minimum of [l, r).
    ll query(int l, int r) {
        pushPath(l + n);
        pushPath(r + n - 1);

        ll ans = INF;

        for (l += n, r += n; l < r;
             l /= 2, r /= 2) {

            if (l & 1) ans = min(ans, st[l++]);
            if (r & 1) ans = min(ans, st[--r]);
        }

        return ans;
    }

    // Find the leftmost valid leaf inside a node.
    int descend(int p, ll x) {
        while (p < n) {
            push(p);
            p *= 2;

            if (st[p] >= x)
                p++;
        }

        return p - n;
    }

    // First i in [l, r) with A[i] < x.
    // Returns -1 if there is no such position.
    int firstBelow(int l, int r, ll x) {
        if (l == r) return -1;

        pushPath(l + n);
        pushPath(r + n - 1);

        vector<int> right;

        for (l += n, r += n; l < r;
             l /= 2, r /= 2) {

            if (l & 1) {
                if (st[l] < x)
                    return descend(l, x);
                l++;
            }

            if (r & 1)
                right.push_back(--r);
        }

        for (int i = (int)right.size() - 1;
             i >= 0; i--) {

            int p = right[i];

            if (st[p] < x)
                return descend(p, x);
        }

        return -1;
    }
};

The implementation has three main ideas worth remembering.

First, apply updates the minimum immediately, so we can answer queries using a node even when its children haven't received the pending addition.

Second, pushPath and pullPath work only along the two boundary paths. We never need to propagate every node selected by the interval decomposition.

Third, pull preserves the invariant by including lazy[p]. This is why rebuilding a node doesn't destroy an update that has not reached its children.

Let's try a small example:

int main() {
    vector<ll> a = {7, 3, 8, 5, 9};

    SegTree st(a);

    st.add(1, 4, 4);
    // a = {7, 7, 12, 9, 9}

    cout << st.query(0, 5) << '\n';
    // 7

    cout << st.firstBelow(2, 5, 10) << '\n';
    // 3
}

The padded leaves contain INF, the neutral value for minimum queries. As long as we operate within the original array and the values remain safely within the range of long long, they won't affect our answers.

We can do more than calculate a minimum

Now suppose we need to answer a slightly different question:

Given $$$l$$$, $$$r$$$, and $$$x$$$, find the smallest index $$$i$$$ such that

$$$ l \le i \lt r \quad\text{and}\quad A_i \lt x. $$$

One possible approach is to binary search over the answer and repeatedly query the minimum of a prefix. That would cost $$$O(\log^2 N)$$$.

But we already know how to decompose an interval into $$$O(\log N)$$$ nodes. Why not use that decomposition directly?

Recall that each node stores the minimum of its segment.

If a node has

$$$ st[p] \ge x, $$$

then none of the elements in that segment can satisfy our condition. We can skip the entire segment.

Otherwise, the segment contains at least one valid answer.

So we can process the selected nodes from left to right until we find the first one whose minimum is below $$$x$$$. Once we find it, we descend through that node, always trying the left child first.

If the left child's minimum is below $$$x$$$, the answer must be somewhere inside it. Otherwise, we move to the right child.

Eventually, we reach the first valid leaf.

This also explains the right vector in firstBelow. During the iterative decomposition, we discover the left-side nodes in left-to-right order, but the right-side nodes in the opposite order. We save those right-side nodes and process them in reverse so that we always search from left to right.

The number of selected nodes is $$$O(\log N)$$$, and we perform at most one additional descent of length $$$O(\log N)$$$. Therefore, the entire search is still:

$$$ \boxed{O(\log N)}. $$$

There is an important detail here: our query is not binary searching because the individual elements are sorted. They don't need to be sorted at all.

We are using the minimum stored in each node to eliminate entire segments that cannot contain an answer.

This is the idea behind guided segment-tree searches, including operations such as max_right and min_left in AtCoder Library.

I think this is a particularly useful way to look at segment trees. They don't just answer questions about an interval; they can also help us locate where a condition first becomes true or false, provided our stored information lets us safely reject entire segments.

For example, imagine tracking the remaining capacity of a resource across different time slots. A reservation decreases the capacity of an interval, while a cancellation increases it.

With the same structure, we can update capacities, obtain the minimum remaining capacity, or find the first time slot whose capacity falls below a chosen threshold.

Of course, this kind of search is possible with recursive segment trees too. The advantage here is that we can derive it naturally from the same iterative decomposition we already understand.

What I would remember instead of the code

There are many implementations of iterative segment trees, and I'm certainly not claiming this technique is new. In particular, I recommend reading Al.Cash's Efficient and easy segment trees and the AtCoder Lazy Segment Tree documentation, which cover these ideas and their generalizations.

What I wanted to contribute was a way of connecting the operations to the properties that make them work.

If I had to reconstruct this implementation during a contest, I would start with three questions:

  1. What does each node represent? Define the aggregate and the invariant that must hold when updates are pending.
  2. Which nodes can affect my answer? For an interval, understand its canonical decomposition and the two boundary paths.
  3. Can my aggregate eliminate an entire segment? If so, perhaps I can turn a range query into a guided search.

I also think it's worth remembering that this implementation is specifically designed for range addition and range minimum. Other combinations of updates and queries may require different stored information, different lazy tags, or different rules for composing updates. The general idea transfers, but the formulas should always be derived rather than copied blindly.

Back in 2023, I spent a week trying to understand something that already had several existing explanations. Looking back, I don't think that time was wasted. It taught me that understanding why a structure works can be just as valuable as learning how to implement it.

I hope this explanation helps someone who has looked at an iterative lazy segment tree and wondered where all those operations came from.

Thank you for reading! If you notice a mistake, have a different way of explaining these properties, or know an interesting application, I'd be happy to discuss it in the comments.

Happy coding!

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

»
18 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Good blog! New overkill technique learned:p