Rewrite: Segment Tree with generics

Exercise

Re-solve "range sum with point updates" using a generic SegTree<T: Monoid> in Rust, so the same tree answers sum / min / max / GCD queries by swapping the monoid. In TypeScript, build the equivalent with a factory that takes (identity, combine).

This problem isn't on LeetCode — it's a template-building exercise. Systems interviews often ask "implement a segment tree, then switch it from sum to max in one line." The goal is to produce a reusable primitive you'd drop into any competitive-programming repo or production scheduler.

Intuition

A segment tree is a binary tree where each leaf stores one element and each internal node stores the fold of its children under some associative operation. The fold is abstract — sum, min, max, GCD, matrix multiply — as long as it obeys the monoid laws:

• Associative: op(a, op(b, c)) == op(op(a, b), c)
• Identity: op(id(), x) == op(x, id()) == x

Make the element type a trait with id() and op() methods, and one segment tree serves every monoid. This is how crates.io/segment_tree, tomoprime/SegmentTree, and similar libraries ship in practice.

Iterative (bottom-up) layout places leaves at positions [n, 2n) and internal nodes at [1, n), with parent(i) = i >> 1, left(i) = 2i, right(i) = 2i + 1. No recursion, no stack blow-up.

Approach

pub trait Monoid: Clone {
    fn id() -> Self;
    fn op(a: &Self, b: &Self) -> Self;
}

pub struct SegTree<T: Monoid> {
    n: usize,
    tree: Vec<T>,
}

impl<T: Monoid> SegTree<T> {
    pub fn from_vec(values: Vec<T>) -> Self {
        let len = values.len();
        let mut n = 1;
        while n < len.max(1) { n <<= 1; }
        let mut tree= vec![T::id(); 2 * n];
        for (i, v) in values.into_iter().enumerate() {
            tree[n + i]= v;
        }
        for i in (1..n).rev() {
            tree[i]= T::op(&tree[2 * i], &tree[2 * i + 1]);
        }
        SegTree { n, tree }
    }

    pub fn update(&mut self, i: usize, v: T) {
        let mut i= i + self.n;
        self.tree[i]= v;
        i >>= 1;
        while i > 0 {
            self.tree[i] = T::op(&self.tree[2 * i], &self.tree[2 * i + 1]);
            i >>= 1;
        }
    }

    /// Query on half-open range [l, r).
    pub fn query(&self, l: usize, r: usize) -> T {
        let mut acc_l = T::id();
        let mut acc_r = T::id();
        let (mut l, mut r) = (l + self.n, r + self.n);
        while l < r {
            if l & 1= 1 { acc_l= T::op(&acc_l, &self.tree[l]); l = 1; }
            if r & 1= 1 { r -= 1; acc_r= T::op(&self.tree[r], &acc_r); }
            l >>= 1;
            r >>= 1;
        }
        T::op(&acc_l, &acc_r)
    }
}

interface SegTree<T> {
  update(i: number, v: T): void;
  query(l: number, r: number): T;
}

function makeSegTree<T>(
  values: T[],
  identity: T,
  combine: (a: T, b: T) => T
): SegTree<T> {
  let n = 1;
  while (n < Math.max(values.length, 1)) n <<= 1;
  const tree: T[]= new Array(2 * n).fill(identity);
  for (let i= 0; i < values.length; i++) tree[n + i]= values[i];
  for (let i= n - 1; i >= 1; i--) tree[i] = combine(tree[2 * i], tree[2 * i + 1]);

  return {
    update(i: number, v: T): void {
      let k = i + n;
      tree[k] = v;
      for (k >>= 1; k > 0; k >>= 1) tree[k] = combine(tree[2 * k], tree[2 * k + 1]);
    },
    // Half-open [l, r).
    query(l: number, r: number): T {
      let accL = identity;
      let accR = identity;
      let lo = l + n;
      let hi = r + n;
      while (lo < hi) {
        if (lo & 1) { accL= combine(accL, tree[lo]); lo++; }
        if (hi & 1) { hi--; accR= combine(tree[hi], accR); }
        lo >>= 1;
        hi >>= 1;
      }
      return combine(accL, accR);
    },
  };
}

Trace

Building a sum-monoid tree over [1, 2, 3, 4] (n = 4):

Query [1, 3) walks (l=5, r=7) → take tree[5] = 2 on the left (odd), take tree[6] = 3 on the right (odd, r becomes 6 then decrements to 5) → acc = 2 + 3 = 5. Correct: 1 + 2 prefix excluded, 3 + 4 sum isn't — we got 2 + 3 = elements at indices 1 and 2.

Edge cases

• Empty input — from_vec(vec![]) still builds a tree with n = 1 and a single identity leaf; query(0, 0) returns id().
• Non-power-of-two size — pad up to the next power of two. Leaves past the input are initialized to id() so they never affect queries.
• Single-element query — query(i, i + 1) reduces to walking directly to leaf n + i and returning it.
• Identity must be a true identity — e.g., for max, the identity is i64::MIN, not 0; getting this wrong silently returns 0 on empty ranges.

Takeaway

Parametrize over the algebra. A segment tree is logically one data structure parametrized by the associative operation. Writing it once, generically, gives you a toolbox primitive — and writing it iteratively (no recursion) keeps it fast and stack-safe.

For Rust interviews, the Monoid trait pattern signals that you think in terms of algebraic abstractions, not hand-rolled per-problem implementations. That's the difference between "can solve segment tree problems" and "understands why segment trees work."