jsschools

Segment Tree

A binary tree structure built over an array that supports range queries (sum, min, max) and point updates in O(log n).

Spec ↗

Syntax

class SegmentTree {
  constructor(arr) { this.n = arr.length; this.tree = new Array(4 * arr.length); this.build(arr, 0, 0, arr.length - 1); }
  query(l, r) { ... }   // range sum/min/max
  update(i, val) { ... } // point update
}

Parameters

NameTypeRequiredDescription
arr number[] Yes The source array over which the segment tree is built.

Returns

SegmentTree — A new SegmentTree instance supporting O(log n) range queries and point updates.

Examples

class SegTree {
  #t; #n;
  constructor(arr) {
    this.#n = arr.length;
    this.#t = new Array(4 * this.#n).fill(0);
    this.#build(arr, 1, 0, this.#n - 1);
  }
  #build(arr, node, start, end) {
    if (start === end) { this.#t[node] = arr[start]; return; }
    const mid = (start + end) >> 1;
    this.#build(arr, 2*node, start, mid);
    this.#build(arr, 2*node+1, mid+1, end);
    this.#t[node] = this.#t[2*node] + this.#t[2*node+1];
  }
  query(l, r, node = 1, start = 0, end = this.#n - 1) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.#t[node];
    const mid = (start + end) >> 1;
    return this.query(l, r, 2*node, start, mid) +
           this.query(l, r, 2*node+1, mid+1, end);
  }
  update(idx, val, node = 1, start = 0, end = this.#n - 1) {
    if (start === end) { this.#t[node] = val; return; }
    const mid = (start + end) >> 1;
    if (idx <= mid) this.update(idx, val, 2*node, start, mid);
    else this.update(idx, val, 2*node+1, mid+1, end);
    this.#t[node] = this.#t[2*node] + this.#t[2*node+1];
  }
}
const st = new SegTree([1, 3, 5, 7, 9, 11]);
console.log(st.query(1, 3));  // sum of index 1..3
st.update(1, 10);
console.log(st.query(1, 3));  // after update
Output 
15
22

// Range min segment tree
const arr = [2, 4, 3, 1, 6, 7, 8, 9, 5];
// build with Math.min combiner instead of addition
console.log('Range min query: useful for RMQ problems like LCA');
Output 
Range min query: useful for RMQ problems like LCA

Notes

| Operation | Time | Space | |-------------|---------|-------| | Build | O(n) | O(n) | | Point update | O(log n)| O(1) | | Range query | O(log n)| O(log n) | | Range update*| O(log n)| O(1) | *Range updates (lazy propagation) add complexity but keep O(log n). The tree is stored in a 1-indexed flat array; node i's children are 2i and 2i+1, parent is i/2. Build the tree of size 4*n to be safe. Segment trees support any associative operation (sum, min, max, GCD, XOR). For range updates see "lazy propagation".

See also