Segment Tree is one of the most versatile and powerful data structures in competitive programming and software engineering. If you need to perform range queries and point updates efficiently, a segment tree is your best friend.

🔍 What Is a Segment Tree?

A Segment Tree is a binary tree used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point efficiently.

✨ Common Use-Cases:

• Range Sum Query
• Range Minimum/Maximum Query
• Range GCD/LCM
• Lazy Propagation for Range Updates
• Histogram Range Frequency

📦 Why Not Just Use an Array?

Suppose you have an array and you want to:

• Query the sum of a range arr[l...r]
• Update a specific element arr[i] = x

❌ Brute Force:

• Query: O(n)
• Update: O(1)

✅ Segment Tree:

• Query: O(log n)
• Update: O(log n)

🧱 Building a Segment Tree (Sum Query Example)

Step 1: Representation

Segment Tree is usually stored in an array. For n elements, size of the segment tree = 2 * 2^ceil(log2(n)) - 1

Step 2: Construction

class SegmentTree {
  tree: number[];
  n: number;

  constructor(arr: number[]) {
    this.n = arr.length;
    const size = 2 * Math.pow(2, Math.ceil(Math.log2(this.n))) - 1;
    this.tree = new Array(size).fill(0);
    this.build(arr, 0, this.n - 1, 0);
  }

  private build(arr: number[], start: number, end: number, index: number): number {
    if (start === end) {
      this.tree[index] = arr[start];
      return arr[start];
    }
    const mid = Math.floor((start + end) / 2);
    this.tree[index] =
      this.build(arr, start, mid, 2 * index + 1) +
      this.build(arr, mid + 1, end, 2 * index + 2);
    return this.tree[index];
  }
}

🔍 Querying a Range Sum

query(l: number, r: number): number {
  return this._queryUtil(0, this.n - 1, l, r, 0);
}

private _queryUtil(start: number, end: number, l: number, r: number, index: number): number {
  if (l <= start && r >= end) return this.tree[index];
  if (end < l || start > r) return 0;

  const mid = Math.floor((start + end) / 2);
  return this._queryUtil(start, mid, l, r, 2 * index + 1) +
         this._queryUtil(mid + 1, end, l, r, 2 * index + 2);
}

🔄 Updating a Value

update(pos: number, newValue: number) {
  this._updateUtil(0, this.n - 1, pos, newValue, 0);
}

private _updateUtil(start: number, end: number, pos: number, newValue: number, index: number): number {
  if (pos < start || pos > end) return this.tree[index];
  if (start === end) {
    this.tree[index] = newValue;
    return newValue;
  }

  const mid = Math.floor((start + end) / 2);
  this.tree[index] =
    this._updateUtil(start, mid, pos, newValue, 2 * index + 1) +
    this._updateUtil(mid + 1, end, pos, newValue, 2 * index + 2);
  return this.tree[index];
}

🧪 Example Usage

const arr = [1, 3, 5, 7, 9, 11];
const st = new SegmentTree(arr);

console.log(st.query(1, 3)); // Output: 15 (3+5+7)
st.update(1, 10); // Update index 1 to 10
console.log(st.query(1, 3)); // Output: 22 (10+5+7)

🧠 Key Takeaways

• Segment Trees reduce range query and update time from O(n) to O(log n).
• Ideal for situations with frequent updates and queries.
• Can be extended to range min/max, GCD, and even 2D segment trees.
• Can be modified using lazy propagation for range updates.

💡 Real-World Applications

• Range frequency or sum queries in stock analysis
• Game state queries like range buffs/debuffs
• Handling millions of real-time user analytics
• Geo-tagging and map-based filters in apps