Build Lab: Generic Lazy-Propagating Segment Tree with Range Affine Updates & Queries

1. Algebraic Specification of the Range Affine Lazy Segment Tree

Let each node $v$ covering $[tl, tr]$ of length $\text{len} = tr - tl + 1$ store:

• Data Summary: $\text{sum}[v] = \sum_{i=tl}^{tr} A[i]$.
• Lazy Affine Tag: $(\text{lazyA}[v], \text{lazyB}[v])$, initialized to the identity map $(1, 0)$.

2. Complete Production Implementation: Range Affine Lazy Segment Tree + Verification Suite

/**
 * Production Range Affine Lazy Segment Tree (Struct-of-Arrays TypedArray Layout)
 * Supports:
 *  - rangeAffine(ql, qr, a, b): for i in [ql..qr], A[i] = a * A[i] + b in O(log N)
 *  - rangeAdd(ql, qr, delta):   special case rangeAffine(ql, qr, 1, delta)
 *  - rangeScale(ql, qr, k):     special case rangeAffine(ql, qr, k, 0)
 *  - rangeAssign(ql, qr, val):  special case rangeAffine(ql, qr, 0, val)
 *  - rangeSum(ql, qr):          sum of A[ql..qr] in O(log N)
 *  - maxRight(l, pred):         largest r >= l-1 such that pred(sum(l..r)) is true in O(log N)
 */
class RangeAffineLazySegTree {
  constructor(arr) {
    this.n = arr.length;
    const size = 4 * this.n;
    this.sum = new Float64Array(size);
    this.lazyA = new Float64Array(size).fill(1);
    this.lazyB = new Float64Array(size).fill(0);
    if (this.n > 0) this._build(1, 0, this.n - 1, arr);
  }

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

  _apply(v, len, a, b) {
    this.sum[v] = a * this.sum[v] + b * len;
    this.lazyA[v] = a * this.lazyA[v];
    this.lazyB[v] = a * this.lazyB[v] + b;
  }

  _pushDown(v, tl, tr) {
    const a = this.lazyA[v], b = this.lazyB[v];
    if (a === 1 && b === 0) return;
    const tm = (tl + tr) >> 1;
    this._apply(v << 1, tm - tl + 1, a, b);
    this._apply((v << 1) | 1, tr - tm, a, b);
    this.lazyA[v] = 1;
    this.lazyB[v] = 0;
  }

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

  rangeAdd(ql, qr, delta) {
    this.rangeAffine(ql, qr, 1, delta);
  }

  rangeScale(ql, qr, factor) {
    this.rangeAffine(ql, qr, factor, 0);
  }

  rangeAssign(ql, qr, val) {
    this.rangeAffine(ql, qr, 0, val);
  }

  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, tl, tr);
    const tm = (tl + tr) >> 1;
    return (
      this.rangeSum(ql, qr, v << 1, tl, tm) +
      this.rangeSum(ql, qr, (v << 1) | 1, tm + 1, tr)
    );
  }

  /**
   * Single-pass O(log N) Segment Tree Walk (requires non-negative elements for monotone sum):
   * Returns largest index r in [l-1 .. n-1] such that pred(sum(l..r)) === true.
   */
  maxRight(l, pred) {
    let acc = 0;
    const walk = (v, tl, tr) => {
      if (tr < l) return tr;
      if (tl >= l && pred(acc + this.sum[v])) {
        acc += this.sum[v];
        return tr;
      }
      if (tl === tr) return tl - 1;
      this._pushDown(v, tl, tr);
      const tm = (tl + tr) >> 1;
      const resL = walk(v << 1, tl, tm);
      if (resL < tm) return resL; // Stopped inside left child!
      return walk((v << 1) | 1, tm + 1, tr);
    };
    return walk(1, 0, this.n - 1);
  }
}

3. Complexity Matrix