DSA DSA In Depth
0%
From-Scratch Build

Segment Tree with Affine Lazy Propagation & Monoid Beats

A full segment tree with composable affine lazy tags (f(x) = a*x + b) supporting range add, range multiply, range assign, range sum/min/max queries, and O(log n) first-element tree walk.

~50 min Advanced Lessons: Build Lab: Generic Lazy-Propagating Segment Tree with Range Affine Updates & Queries, Segment Trees over Monoids: Recursive vs Iterative (ZKW) Bottom-Up Implementation, Lazy Propagation & Segment Tree Beats (Ji Driver Segment Tree for Range Chmin/Chmax), Fenwick Trees (Binary Indexed Trees): lowbit Geometry, Point Updates & Range Updates, Dynamic (Sparse) & Persistent Segment Trees: K-th Smallest in Subarray in O(log N), √N Block Decomposition & Mo's Offline Query Ordering (O((N+Q)√N))
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Unifying Add, Multiply, and Assign via Affine Operators

Instead of juggling separate boolean flags for range assignment and range addition, we represent every lazy update as an affine linear transformation:

$$f_{(m, a)}(x) = m \cdot x + a$$

  • Range Add $+\Delta$: $(m, a) = (1, \Delta)$
  • Range Multiply $\times k$: $(m, a) = (k, 0)$
  • Range Assign $= v$: $(m, a) = (0, v)$

When a new operator $g = (m_2, a_2)$ is applied on top of an existing lazy tag $f = (m_1, a_1)$, their composition is closed:

$$g(f(x)) = m_2(m_1 x + a_1) + a_2 = (m_1 m_2) x + (m_2 a_1 + a_2)$$

Over a segment of length $L$, the sum transforms as $S' = m \cdot S + a \cdot L$, while the extrema update in $O(1)$.

$O(\log n)$ Segment Tree Walk

Finding the first index in $[ql, qr]$ with $A[i] \ge \tau$ via binary search on queryRange costs $O(\log^2 n)$. By walking the segment tree directly and pruning any node where $\text{max}[\text{node}] < \tau$, we visit at most $2 \log_2 n$ nodes and solve the query in $O(\log n)$ time.

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Affine Lazy Operator Composition

  • Core Mechanical Concept: Affine Lazy Operator Composition
  • Target Module: index.js (Step1)
  • Engineering Specification: Implement _applyAffine(node, len, mul, add) to update _sum, _min, _max, and compose two affine functions $g(f(x)) = m_2(m_1 x + a_1) + a_2 = (m_1 m_2)x + (a_1 m_2 + a_2)$.
  • Verification Invariant: verifies Step 1: Affine Lazy Operator Composition

Step 2: Lazy Tag Push-Down

  • Core Mechanical Concept: Lazy Tag Push-Down
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement _push(node, start, end) to push pending (_lazyMul, _lazyAdd) tags to both children and reset the parent tag to identity (1, 0).
  • Verification Invariant: verifies Step 2: Lazy Tag Push-Down

Step 3: Range Affine Updates & Aggregate Queries

  • Core Mechanical Concept: Range Affine Updates & Aggregate Queries
  • Target Module: index.js (Step3)
  • Engineering Specification: Implement rangeAffine(ql, qr, mul, add) (which unifies rangeAdd, rangeMultiply, and rangeAssign) and queryRange(ql, qr) returning { sum, min, max }.
  • Verification Invariant: verifies Step 3: Range Affine Updates & Aggregate Queries

Step 4: O(log n) Segment Tree Walk

  • Core Mechanical Concept: O(log n) Segment Tree Walk
  • Target Module: index.js (Step4)
  • Engineering Specification: Implement findFirstAtLeast(ql, qr, threshold) by pruning subtrees where _max[node] < threshold and recursing left before right.
  • Verification Invariant: verifies Step 4: O(log n) Segment Tree Walk

Asymptotic & Memory Layout Guarantees

  • Category: Range Queries & Trees
  • Difficulty: Advanced (~50 minutes)
  • Key Architectural Highlights:
    • Composable affine lazy operator f(x) = mul * x + add supporting range multiply, range add, and range assign
    • Simultaneous maintenance of range sum, minimum, and maximum across all updates
    • O(log n) tree-walk search findFirstAtLeast(l, r, threshold) without binary search overhead
  • Tags & Primitives: Segment Tree, Lazy Propagation, Affine Transformation, Range Sum Min Max, Tree Walk

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.