07 — Trees Advanced (Segment Tree & Fenwick Tree)

Segment Tree

Answer range queries and point updates in O(log n).

Array:  [1, 3, 5, 7, 9, 11]

Segment Tree:
            [36]              sum(0..5)
         /        \
      [9]          [27]       sum(0..2), sum(3..5)
     /   \        /    \
   [4]   [5]   [16]   [11]
   / \         /  \
 [1] [3]     [7]  [9]

class SegmentTree {
  private tree: number[];
  private n: number;
  
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }
  
  private build(arr: number[], node: number, start: number, end: number) {
    if (start === end) {
      this.tree[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.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
  
  // Point update: arr[idx] = val
  update(idx: number, val: number, node = 1, start = 0, end = this.n - 1) {
    if (start === end) {
      this.tree[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.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
  
  // Range query: sum(l..r)
  query(l: number, r: number, node = 1, start = 0, end = this.n - 1): number {
    if (r < start || end < l) return 0;           // Out of range
    if (l <= start && end <= r) return this.tree[node]; // Fully in range
    const mid = (start + end) >> 1;
    return this.query(l, r, 2 * node, start, mid) +
           this.query(l, r, 2 * node + 1, mid + 1, end);
  }
}

// Usage
const st = new SegmentTree([1, 3, 5, 7, 9, 11]);
st.query(1, 4);    // sum(index 1..4) = 3+5+7+9 = 24
st.update(2, 10);  // arr[2] = 10
st.query(1, 4);    // 3+10+7+9 = 29

Operations

---

Fenwick Tree (Binary Indexed Tree)

Simpler than Segment Tree for prefix sum queries and point updates.

class FenwickTree {
  private tree: number[];
  private n: number;
  
  constructor(n: number) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }
  
  // Add val to index i (1-indexed)
  update(i: number, val: number) {
    for (; i <= this.n; i += i & (-i)) {
      this.tree[i] += val;
    }
  }
  
  // Prefix sum [1..i]
  query(i: number): number {
    let sum = 0;
    for (; i > 0; i -= i & (-i)) {
      sum += this.tree[i];
    }
    return sum;
  }
  
  // Range sum [l..r]
  rangeQuery(l: number, r: number): number {
    return this.query(r) - this.query(l - 1);
  }
}

// Build from array
const bit = new FenwickTree(6);
const arr = [1, 3, 5, 7, 9, 11];
arr.forEach((v, i) => bit.update(i + 1, v)); // 1-indexed

bit.rangeQuery(2, 5); // sum(index 2..5) = 3+5+7+9 = 24
bit.update(3, 5);     // Add 5 to index 3

i & (-i) gives the lowest set bit — determines the range each node covers.

---

Sparse Table

Static range queries in O(1) after O(n log n) build. No updates.

class SparseTable {
  private table: number[][];
  private log: number[];
  
  constructor(arr: number[]) {
    const n = arr.length;
    const k = Math.floor(Math.log2(n)) + 1;
    this.table = Array.from({ length: k }, () => new Array(n));
    this.log = new Array(n + 1);
    
    this.log[1] = 0;
    for (let i = 2; i <= n; i++) this.log[i] = this.log[i >> 1] + 1;
    
    // Build: table[j][i] = min of range [i, i + 2^j - 1]
    for (let i = 0; i < n; i++) this.table[0][i] = arr[i];
    
    for (let j = 1; j < k; j++) {
      for (let i = 0; i + (1 << j) - 1 < n; i++) {
        this.table[j][i] = Math.min(
          this.table[j - 1][i],
          this.table[j - 1][i + (1 << (j - 1))]
        );
      }
    }
  }
  
  // Range min query O(1)
  query(l: number, r: number): number {
    const j = this.log[r - l + 1];
    return Math.min(this.table[j][l], this.table[j][r - (1 << j) + 1]);
  }
}

---

Comparison

---

Key Takeaways

• Segment Tree: most versatile — range query + point/range update; O(log n)
• Fenwick Tree: simpler, less space — prefix sums + point update
• Sparse Table: O(1) queries but no updates — static min/max/GCD
• Segment Tree uses 2*node and 2*node+1 for children
• Fenwick Tree uses i & (-i) for index manipulation (1-indexed)