Segment Tree

What you'll learn

• What Is It?

  A segment tree is a binary tree data structure that allows efficient range queries and point/range updates on an array. Each node stores aggregate information (sum, min, max, etc.) for a contiguous segment of the array. When to use: You…

• Structure

  A segment tree for an array of size n: - Has 2n nodes (stored in array of size 2n) - Leaves (indices n to 2n-1) hold original array values - Internal nodes hold aggregate of their children - Root (index 1) holds aggregate of entire array…

• Implementation (Iterative, Bottom-Up)

  This is the most efficient and concise segment tree implementation: Why the array is size 2n: - Indices 1 to n-1: internal nodes - Indices n to 2n-1: leaves (original array) - Index 0 is unused (makes parent/child math clean: parent = i/…

• Walkthrough: Query [1, 4] on Array [1, 3, 5, 7, 9, 11]

  ---

• Walkthrough: Update index 2 to value 10

  ---

• Segment Tree for Min/Max

  Simply replace + with min or max: ---

• Lazy Propagation (Range Updates)

  When you need to update an entire range efficiently (e.g., "add 5 to all elements in [L, R]"), lazy propagation defers updates to children until they are actually needed. Concept: - Each node has a lazy value representing pending updates…

• Fenwick Tree (Binary Indexed Tree) - Alternative

  For simpler use cases (point update + prefix sum query), a Fenwick tree is more memory-efficient and has lower constant factors: Key insight: i & (-i) isolates the lowest set bit, which determines the range each node is responsible for. ---

• Segment Tree vs Fenwick Tree

  | Feature | Segment Tree | Fenwick Tree | |---------|-------------|--------------| | Range query | Yes (any aggregate) | Yes (prefix-based only) | | Point update | Yes | Yes | | Range update | Yes (with lazy) | Limited (add to range) | |…

• Common Applications

  | Problem Type | Approach | |-------------|----------| | Range sum + point updates | Basic segment tree or Fenwick | | Range min/max + point updates | Segment tree | | Range updates + range queries | Segment tree with lazy propagation |…

• Coordinate Compression + Segment Tree

  When values are large but count is small, compress values to ranks: