Segment Trees over Monoids: Recursive vs Iterative (ZKW) Bottom-Up Implementation

1. Why Recursive Segment Trees Need $4N$ Space While Iterative Needs $2N$

In a top-down recursive segment tree using 1-based heap indexing ($\text{left} = 2v$, $\text{right} = 2v+1$), if $N = 2^k + 1$ (just over a power of two), the tree has height $k + 2$, and the rightmost leaves at the deepest level can reach index $\approx 4N - 5$. Hence recursive implementations must allocate $4N$ entries.

In an Iterative (ZKW) Segment Tree, we bypass top-down midpoint splitting entirely: we place element $A[i]$ at index $N + i$ (for $0 \le i < N$) and populate internal nodes from $i = N - 1$ down to $1$ using $\text{tree}[i] = \text{tree}[2i] \oplus \text{tree}[2i + 1]$. Every internal node $i \in [1, N-1]$ has two valid children $2i$ and $2i+1$ in $[2, 2N-1]$, requiring exactly $2N$ elements for any $N$ (even when $N$ is not a power of two!).

2. Designing Non-Trivial Monoids: Dynamic Range Maximum Subarray Sum

How do we answer "what is the maximum contiguous subarray sum inside $A[L..R]$" under point updates? A single scalar is not closed under concatenation because the optimal subarray across $L \cup R$ might straddle the boundary between the left child and the right child. We lift each node to a 4-tuple monoid state $(S, P, Q, M)$:

• $S$: Total sum of the segment ($S = S_L + S_R$)
• $P$: Maximum prefix sum of the segment ($P = \max(P_L, S_L + P_R)$)
• $Q$: Maximum suffix sum of the segment ($Q = \max(Q_R, Q_L + S_R)$)
• $M$: Maximum subarray sum anywhere in the segment ($M = \max(M_L, M_R, Q_L + P_R)$)

3. Production Implementation: Generic Non-Commutative Iterative Segment Tree & Max Subarray Monoid

/**
 * Generic Iterative (ZKW) Segment Tree over any Monoid (M, combine, identity)
 * Space: Exact 2N | Build: O(N) | Point Update & Range Query: O(log N)
 */
class MonoidSegmentTree {
  constructor(arr, combine, identity) {
    this.n = arr.length;
    this.combine = combine;
    this.identity = identity;
    this.tree = new Array(2 * this.n);
    for (let i = 0; i < this.n; i++) {
      this.tree[this.n + i] = arr[i];
    }
    for (let i = this.n - 1; i >= 1; i--) {
      this.tree[i] = combine(this.tree[i << 1], this.tree[(i << 1) | 1]);
    }
  }

  // Point replacement: A[idx] = val (0-indexed)
  set(idx, val) {
    let p = idx + this.n;
    this.tree[p] = val;
    for (p >>= 1; p >= 1; p >>= 1) {
      this.tree[p] = this.combine(this.tree[p << 1], this.tree[(p << 1) | 1]);
    }
  }

  // Range query over closed interval [l, r] (0-indexed), preserving non-commutative order!
  query(l, r) {
    let resL = this.identity;
    let resR = this.identity;
    for (let a = l + this.n, b = r + this.n + 1; a < b; a >>= 1, b >>= 1) {
      if (a & 1) resL = this.combine(resL, this.tree[a++]);
      if (b & 1) resR = this.combine(this.tree[--b], resR);
    }
    return this.combine(resL, resR);
  }
}

// Example: Maximum Subarray Sum Monoid (GSS1 / Kadane Monoid)
const KadaneMonoid = {
  identity: { sum: 0, pref: -Infinity, suff: -Infinity, best: -Infinity },
  leaf(x) {
    return { sum: x, pref: x, suff: x, best: x };
  },
  combine(L, R) {
    if (L.best === -Infinity) return R;
    if (R.best === -Infinity) return L;
    return {
      sum: L.sum + R.sum,
      pref: Math.max(L.pref, L.sum + R.pref),
      suff: Math.max(R.suff, L.suff + R.sum),
      best: Math.max(L.best, R.best, L.suff + R.pref)
    };
  }
};

4. Complexity Matrix