Segment Tree Lazy

Learn about Segment Tree Lazy with interactive visualizations and depth. Optimize range queries with Lazy Propagation for high-performance applications.

1. The Problem: Range Updates

A standard Segment Tree is perfect for Point Updates in O(log N). But what if we want to increment a range of indices, say [0...1000], by 5?

• Naive Segment Tree: Must recursively update all 1000 individual leaves. This degrades to O(N) or O(N log N) time per range update.
• Lazy Propagation: Update the high-level nodes and “flag” them with the pending updates. Don’t propagate the updates to the children until you actually need to visit them later.
• Result: Range Update in O(log N).

Core Concept

Lazy Propagation defers the execution of updates. We record an update at a high-level segment tree node and only push it down to its children when a subsequent query or update forces us to visit them.

---

2. Mathematical Anchor: Why 4N Space?

Why do we always declare the Segment Tree array as tree = new int[4 * n]?

1. A Segment Tree is a Binary Tree.
2. The leaves represent the N array elements.
3. A strictly binary tree with N leaves has N - 1 internal nodes.
4. Total nodes = 2N - 1.
5. However, we use an Array to represent the tree (like a Binary Heap). If N is not a power of 2, the tree is not a perfect binary tree. We need padding to ensure that children 2 * i and 2 * i + 1 exist even for empty branches near the bottom.
6. The Math: The next power of 2 greater than or equal to N can be at most 2N - 1 (roughly 2N). The array size for a perfect binary tree of 2N leaves is 2 * (2N) = 4N.

---

3. Intuition: The “Manager Analogy”

Imagine a CEO (Root) wants to give a $1000 bonus to all employees in the engineering department (a subset of Leaves).

• Without Lazy: The CEO walks to every single engineer’s desk to hand them the money. (Slow, exhaustive traversal).
• With Lazy: The CEO tells the Engineering Department Head (a high-level Node), “Here is $1000 for everyone under you. Keep this money on your desk, and distribute it down only if someone asks.”
• Push: When an employee or a lower-level manager is explicitly queried (e.g., HR asks for an individual’s total compensation), then the Department Head passes the “lazy” bonus note down to the Team Leads, who may pass it further down.

---

4. Interactive Lazy Propagation Visualization

Below is an interactive segment tree. We have an array of 4 elements initially all 0. Click the buttons to perform range updates and queries, and watch how the tree and lazy values change!

[0, 3]

Sum: 0

[0, 1]

Sum: 0

[2, 3]

Sum: 0

[0, 0]

0

[1, 1]

0

[2, 2]

0

[3, 3]

0

Ready.

---

5. The Architecture of Lazy Propagation

To properly implement a Lazy Segment Tree, we typically maintain two arrays:

1. tree[]: The actual Segment Tree holding our range queries (e.g., Sum, Min, Max).
2. lazy[]: An array parallel to tree[]. If lazy[node] != 0, it means this node has pending updates that have not yet been passed down to its children.

The Push Method (Resolving Lazy)

Before a node is updated or queried, it must resolve its pending lazy value. This is typically abstracted into a push or resolveLazy method.

void push(int node, int start, int end) {
    if (lazy[node] != 0) {
        // 1. Apply the pending update to this node
        tree[node] += (end - start + 1) * lazy[node]; // Multiply by range length for Sum queries

        // 2. If it's not a leaf, pass the lazy value down
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }

        // 3. Clear the lazy value for this node
        lazy[node] = 0;
    }
}

---

6. Implementation Skeleton

Here is the complete code for a Lazy Segment Tree supporting Range Sum Queries and Range Addition Updates.

Java

Go

public class LazySegmentTree {
    int[] tree, lazy;

    public LazySegmentTree(int n) {
        tree = new int[4 * n];
        lazy = new int[4 * n];
    }

    // Push pending lazy updates down
    private void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    public void update(int node, int start, int end, int l, int r, int val) {
        // 1. Resolve Lazy value if exists
        push(node, start, end);

        // 2. Out of Range
        if (start > end || start > r || end < l) return;

        // 3. Fully In Range
        if (start >= l && end <= r) {
            // Apply lazy update here directly, then push
            lazy[node] += val;
            push(node, start, end);
            return;
        }

        // 4. Partial Overlap -> Recurse
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r, val);
        update(2 * node + 1, mid + 1, end, l, r, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    public int query(int node, int start, int end, int l, int r) {
        // 1. Always push before querying!
        push(node, start, end);

        // 2. Out of Range
        if (start > end || start > r || end < l) return 0;

        // 3. Fully In Range
        if (start >= l && end <= r) return tree[node];

        // 4. Partial Overlap -> Recurse
        int mid = (start + end) / 2;
        int leftSum = query(2 * node, start, mid, l, r);
        int rightSum = query(2 * node + 1, mid + 1, end, l, r);
        return leftSum + rightSum;
    }
}

type LazySegmentTree struct {
	tree []int
	lazy []int
}

func NewLazySegmentTree(n int) *LazySegmentTree {
	return &LazySegmentTree{
		tree: make([]int, 4*n),
		lazy: make([]int, 4*n),
	}
}

// Push pending lazy updates down
func (st *LazySegmentTree) push(node, start, end int) {
	if st.lazy[node] != 0 {
		st.tree[node] += (end - start + 1) * st.lazy[node]
		if start != end {
			st.lazy[2*node] += st.lazy[node]
			st.lazy[2*node+1] += st.lazy[node]
		}
		st.lazy[node] = 0
	}
}

func (st *LazySegmentTree) Update(node, start, end, l, r, val int) {
	// 1. Resolve Lazy value if exists
	st.push(node, start, end)

	// 2. Out of Range
	if start > end || start > r || end < l {
		return
	}

	// 3. Fully In Range
	if start >= l && end <= r {
		st.lazy[node] += val
		st.push(node, start, end)
		return
	}

	// 4. Partial Overlap -> Recurse
	mid := (start + end) / 2
	st.Update(2*node, start, mid, l, r, val)
	st.Update(2*node+1, mid+1, end, l, r, val)
	st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}

func (st *LazySegmentTree) Query(node, start, end, l, r int) int {
	// 1. Always push before querying!
	st.push(node, start, end)

	// 2. Out of Range
	if start > end || start > r || end < l {
		return 0
	}

	// 3. Fully In Range
	if start >= l && end <= r {
		return st.tree[node]
	}

	// 4. Partial Overlap -> Recurse
	mid := (start + end) / 2
	leftSum := st.Query(2*node, start, mid, l, r)
	rightSum := st.Query(2*node+1, mid+1, end, l, r)
	return leftSum + rightSum
}

---

7. Complexity Analysis

Operation	Time Complexity	Space Complexity	Description
Build Tree	O(N)	O(N)	Initializing the tree takes linear time. Array size is 4N.
Point Update	O(log N)	O(1)	Traverse down to leaf and update nodes on the way back up.
Range Update	O(log N)	O(1)	Uses Lazy Propagation to update segments. Halts descent early when segment is completely contained within the query range.
Range Query	O(log N)	O(1)	Resolves lazy values (push) before reading values to ensure accuracy.

Summary: When to use Lazy Segment Tree?

If your problem requires both Range Queries (Sum, Min, Max, XOR) and Range Updates (Add X to [L, R], Set [L, R] to X), and the constraints are up to 10^5, you must use a Lazy Segment Tree or a similar structure (like a Binary Indexed Tree, if the problem allows).