Segment Trees Crash Course

Introduction

• Segment Trees are used for range queries.
• Alternatives include Fenwick trees, prefix sums.
• This course walks through the basics, implementations, and advanced topics like lazy propagation.

Why Segment Trees?

• Versatility: Handles multiple complex range queries and updates efficiently.
• # of Ranges: Unlike Fenwick trees, it can handle queries in any range, not just from the start to an end.
• Non-Invertibility: Handles operations where values are not easily invertible (e.g., min, max operations).
• Memory Efficiency: Requires O(4N) memory.

Segment Tree Basics

• Concept: Break down array into segments and build a tree structure where each node represents a segment.
• Range Operations: Supports range queries for sums, min, max, etc.

Building the Segment Tree

• Initialization: Represented in an array to save space, the tree is built top-down using a DFS approach.
• Implementation: Use indexes to represent tree nodes and their children, avoiding pointer overhead.
• *Pseudocode: Build Function:

  build(a, v, tl, tr) {
    if tl == tr {
      t[v] = a[tl];
    } else {
      tm = (tl + tr)/2;
      build(a, 2*v, tl, tm);
      build(a, 2*v+1, tm+1, tr);
      t[v] = t[2*v] + t[2*v+1];
    }
  }
  

Querying the Segment Tree

• Process: Queries traverse the tree and gather results only from necessary segments using DFS.
• Complexity: O(log n)
• Pseudocode: Query Function:

  query(v, tl, tr, l, r) {
    if l > r {
      return 0; // Identity element for sum
    }
    if l == tl && r == tr {
      return t[v];
    }
    tm = (tl + tr) / 2;
    return query(2*v, tl, tm, l, min(r, tm)) + query(2*v+1, tm+1, tr, max(l, tm+1), r);
  }
  

Updating the Segment Tree (Point Update)

• Process: Traverse to the target index and update, then backtrack to update parent nodes.
• Complexity: O(log n)
• Pseudocode: Update Function:

  update(v, tl, tr, pos, new_val) {
    if tl == tr {
      t[v] = new_val;
    } else {
      tm = (tl + tr) / 2;
      if pos <= tm
        update(2*v, tl, tm, pos, new_val);
      else
        update(2*v+1, tm+1, tr, pos, new_val);
      t[v] = t[2*v] + t[2*v+1];
    }
  }
  

Lazy Propagation

• Use Case: Efficiently handle range updates by deferring updates to child nodes until required.
• Components: Lazy array to store deferred updates.
• Implementation: Modify build, update, and query functions to handle deferred updates.
• Pseudocode: Push & Update Functions:

  push(v) {
    if lazy[v] != 0 {
      t[2*v] += lazy[v];
      lazy[2*v] += lazy[v];
      t[2*v+1] += lazy[v];
      lazy[2*v+1] += lazy[v];
      lazy[v] = 0;
    }
  }
  updateRange(v, tl, tr, l, r, addend) {
    if l > r return;
    if l == tl && tr == r {
      t[v] += addend;
      lazy[v] += addend;
    } else {
      push(v); // Push pending updates
      tm = (tl + tr) / 2;
      updateRange(2*v, tl, tm, l, min(r, tm), addend);
      updateRange(2*v+1, tm+1, tr, max(l, tm+1), r, addend);
      t[v] = t[2*v] + t[2*v+1];
    }
  }
  

Advanced Topics

• Generic Segment Tree: Modularize different operations using templates for node and update structures.
  • Node Class: Handles the storage and merging of segment values.
  • Update Class: Manages the combination and application of updates.
• Complex Queries: Various examples provided, such as range minimum with counts, value setting, multiplication operations.

Conclusion

• Segment trees, particularly with lazy propagation, offer powerful ways to handle complex range queries and updates.
• The course covers theoretical concepts, practical coding implementations, and advanced modularization techniques.
• Numerous examples and practice problems are available to improve understanding.