Lazy Propagation & Segment Tree Beats (Ji Driver Segment Tree for Range Chmin/Chmax)

1. The Algebraic Axioms of Lazy Propagation (Monoid Action)

Formally, a Lazy Segment Tree requires two monoids and a distributive action:

1. Data Monoid $(S, \oplus, e_S)$: Combines left and right child summaries (pull / pushUp), e.g., $(S_L + S_R, \text{len}_L + \text{len}_R)$.
2. Tag (Endomorphism) Monoid $(F, \circ, \text{id}_F)$: Composes a new lazy operation $f_{\text{new}}$ onto an existing pending tag $f_{\text{old}}$ via $f_{\text{new}} \circ f_{\text{old}}$. For range affine updates $f(x) = ax + b$, composing $f_2(x) = a_2 x + b_2$ after $f_1(x) = a_1 x + b_1$ yields $f_2(f_1(x)) = (a_2 a_1)x + (a_2 b_1 + b_2)$.
3. Distributive Mapping $F \times S \to S$: For any tag $f \in F$ and states $s_1, s_2 \in S$, applying $f$ distributes over $\oplus$: $f(s_1 \oplus s_2) = f(s_1) \oplus f(s_2)$.

2. Production Implementation: Segment Tree Beats (Range Chmin + Range Sum)

/**
 * Ji Driver Segment Tree (Segment Tree Beats)
 * Supports:
 *  - rangeChmin(ql, qr, x): for i in [ql..qr], A[i] = Math.min(A[i], x) in O(log N) amortized
 *  - rangeSum(ql, qr): sum of A[ql..qr] in O(log N)
 *  - rangeMax(ql, qr): max of A[ql..qr] in O(log N)
 */
class SegmentTreeBeats {
  constructor(arr) {
    this.n = arr.length;
    const size = 4 * this.n;
    this.sum = new Float64Array(size);
    this.max1 = new Float64Array(size);
    this.max2 = new Float64Array(size);
    this.cntMax = new Int32Array(size);
    this._build(1, 0, this.n - 1, arr);
  }

  _build(v, tl, tr, arr) {
    if (tl === tr) {
      this.sum[v] = arr[tl];
      this.max1[v] = arr[tl];
      this.max2[v] = -Infinity;
      this.cntMax[v] = 1;
      return;
    }
    const tm = (tl + tr) >> 1;
    this._build(v << 1, tl, tm, arr);
    this._build((v << 1) | 1, tm + 1, tr, arr);
    this._pull(v);
  }

  _pull(v) {
    const L = v << 1, R = L | 1;
    this.sum[v] = this.sum[L] + this.sum[R];
    if (this.max1[L] === this.max1[R]) {
      this.max1[v] = this.max1[L];
      this.max2[v] = Math.max(this.max2[L], this.max2[R]);
      this.cntMax[v] = this.cntMax[L] + this.cntMax[R];
    } else if (this.max1[L] > this.max1[R]) {
      this.max1[v] = this.max1[L];
      this.max2[v] = Math.max(this.max2[L], this.max1[R]);
      this.cntMax[v] = this.cntMax[L];
    } else {
      this.max1[v] = this.max1[R];
      this.max2[v] = Math.max(this.max1[L], this.max2[R]);
      this.cntMax[v] = this.cntMax[R];
    }
  }

  _applyChmin(v, x) {
    if (x >= this.max1[v]) return;
    this.sum[v] -= (this.max1[v] - x) * this.cntMax[v];
    this.max1[v] = x;
  }

  _pushDown(v) {
    // Parent's max1 acts as an implicit upper-bound clamp on both children!
    this._applyChmin(v << 1, this.max1[v]);
    this._applyChmin((v << 1) | 1, this.max1[v]);
  }

  rangeChmin(ql, qr, x, v = 1, tl = 0, tr = this.n - 1) {
    if (ql > tr || qr < tl || x >= this.max1[v]) return; // Case 1: Break
    if (ql <= tl && tr <= qr && x > this.max2[v]) {     // Case 2: Tag
      this._applyChmin(v, x);
      return;
    }
    this._pushDown(v);                                   // Case 3: Recurse
    const tm = (tl + tr) >> 1;
    this.rangeChmin(ql, qr, x, v << 1, tl, tm);
    this.rangeChmin(ql, qr, x, (v << 1) | 1, tm + 1, tr);
    this._pull(v);
  }

  rangeSum(ql, qr, v = 1, tl = 0, tr = this.n - 1) {
    if (ql > tr || qr < tl) return 0;
    if (ql <= tl && tr <= qr) return this.sum[v];
    this._pushDown(v);
    const tm = (tl + tr) >> 1;
    return (
      this.rangeSum(ql, qr, v << 1, tl, tm) +
      this.rangeSum(ql, qr, (v << 1) | 1, tm + 1, tr)
    );
  }
}

3. Complexity Matrix