Segment Tree

A segment tree is a binary tree data structure that allows answering range queries and updating values in an array in logarithmic time. Each leaf node of the segment tree represents a single element of the array, and each non-leaf node represents a segment (or range) of the array, covering the elements of its children.

Visualization

Why Segment Trees

Consider a scenario where we have an array of numbers, and we want to frequently update its values and also compute the sum of a range of elements. One could iterate through the range and calculate the sum. The array update will be O(1) and the range query will be O(n), but this would be inefficient with frequent queries. Segment trees make these operations efficient, performing both tasks in O(log n) time.

Anatomy of the Segment Tree

• Leaves: The leaves of the tree represent individual elements of the input array.
• Internal Nodes: Every internal node represents some segment of the array. For instance, if the left and right children of a node represent the ranges [a, b] and [c, d] respectively, then the parent node represents the range [a, d].

Operations

We can use linked-list tree data structure to store the binary tree but it will use significant overhead on each element for the left and right pointer. Instead, we can use array-based tree which allows easy access to left child and right child from any node using simple arithmetic. For example, if we store the root at index 1, then given any node at position index, we can access its children:

• Left child: index * 2
• Right child: index * 2 + 1

The number of nodes needed in this case 2 * 2^ceil(log2(n)) - 1, since we store root at 1, so the array length needed is 2 * 2^ceil(log2(n)) (need to check the visualization and implementation to see this)

Building the Tree O(n)

function build(tree: number[], node: number, a: number[], start: number, end: number): number {
  if (start === end) {
    tree[node] = a[start]
  } else {
    const mid = Math.floor((start + end) / 2)
    const left = build(tree, node * 2, a, start, mid)
    const right = build(tree, node * 2 + 1, a, mid + 1, end)
    
    tree[node] = left + right
  }

  return tree[node]
}

Querying O(log n)

function query(tree: number[], node: number, start: number, end: number, l: number, r: number): number {
  // query range out of the current segment
  if (l > end || r < start) {
    return 0
  }

  // query range includes the whole current segment
  if (l <= start && r >= end) {
    return tree[node]
  }

  const mid = Math.floor((start + end) / 2)

  // start query on left and right
  const rs = query(tree, node * 2, start, mid, l, r) + query(tree, node * 2, mid + 1, end, l, r)

  return rs
}

Updating O(log n)

function update(tree: number[], node: number, start: number, end: number, ind: number, value: number): number {
  if (start === end && start === ind) {
    tree[node] = value
  } else {
    const mid = Math.floor((start + end) / 2)
    
    if (ind >= start && ind <= mid) {
      update(tree, node*2, start, mid, ind, value)
    } else if (ind >= mid + 1 && ind <= end) {
      update(tree, node*2 + 1, mid+1, end, ind, value)
    }
    
    tree[node] = tree[node*2] + tree[node*2 + 1]
  }

  return tree[node]
}

Using the above

export class SegmentTree {
  tree: number[] = []
  len: number

  constructor(a: number[]) {
    this.len = a.length
    build(this.tree, 1, a, 0, a.length - 1)
  }

  update(ind: number, val: number) {
    update(this.tree, 1, 0, this.len - 1, ind, val)
  }

  query(l: number, r: number): number {
    return query(this.tree, 1, 0, this.len - 1, l, r)
  }
}

Applications

Segment trees can be used for:

• Sum of a given range.
• Finding the minimum/maximum of a range.
• GCD of a range.
• Lazy propagation (an optimization for range updates).
• And more!