Segment Tree Pattern

When to use Segment Tree

• The problem mixes range queries (sum, min, max over a subarray) with point updates that change individual elements.
• A naive prefix-sum solution would re-compute the entire prefix array on every update, giving O(n) per update.
• The aggregate operation is associative — sum, min, max, gcd, xor — so partial results from child nodes can be combined into a parent result.
• You need to answer many queries (thousands or more) against an array that also mutates many times.
• The input size is in the 10^4 to 10^5 range where O(n) per query is too slow but O(log n) is comfortable.

Template

class SegmentTree {
  constructor(nums) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(0);
    if (this.n > 0) this.build(nums, 1, 0, this.n - 1);
  }
  build(nums, node, start, end) {
    if (start === end) {
      this.tree[node] = nums[start];
      return;
    }
    const mid = (start + end) >> 1;
    this.build(nums, 2 * node, start, mid);
    this.build(nums, 2 * node + 1, mid + 1, end);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
  update(index, value) {
    this._update(1, 0, this.n - 1, index, value);
  }
  _update(node, start, end, index, value) {
    if (start === end) {
      this.tree[node] = value;
      return;
    }
    const mid = (start + end) >> 1;
    if (index <= mid) this._update(2 * node, start, mid, index, value);
    else this._update(2 * node + 1, mid + 1, end, index, value);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
  query(left, right) {
    return this._query(1, 0, this.n - 1, left, right);
  }
  _query(node, start, end, left, right) {
    if (right < start || end < left) return 0;
    if (left <= start && end <= right) return this.tree[node];
    const mid = (start + end) >> 1;
    return this._query(2 * node, start, mid, left, right) + this._query(2 * node + 1, mid + 1, end, left, right);
  }
}

Common mistakes

• Off-by-one in the build recursion that puts a leaf into the wrong array slot, silently corrupting every query that touches it.
• Allocating only 2n slots instead of 4n — the tree is balanced but not perfectly so, and the last level needs the extra headroom.
• Forgetting to propagate the update up the tree after writing the leaf, leaving stale aggregates at every ancestor.
• Using inclusive vs exclusive range conventions inconsistently between query and update, producing answers that are one element short or one element too long.
• Picking a non-associative aggregate (like average or median) and getting wrong answers because parent nodes cannot be combined from child summaries.