sko.kr

Algorithms - 12. Segment Tree

algorithmsdata-structuressegment-treerange-queriesdivide-and-conquer
By sko•10/8/2025•9 min read

When to use Segment Tree

Use Segment Tree when you need to efficiently perform range queries and point updates on an array. While most commonly used for range sum queries, it can be adapted for:

  • Range sum queries (classic use case)
  • Range minimum/maximum queries (RMQ)
  • Range GCD/LCM queries for mathematical operations
  • Count of elements in a range meeting certain criteria
  • Range update operations (with lazy propagation)
  • Any associative operation that can be computed by combining smaller ranges (XOR, AND, OR, multiplication)

Example problem

Real-time Trading Dashboard: You're building a live trading system that tracks 1 million stocks [s₀, s₁, ..., s₉₉₉,₉₉₉] with thousands of simultaneous users. Every second, your system must handle:

  1. 10,000+ range queries: "What's the total value of stocks 234,567 to 456,789?"
  2. 5,000+ price updates: "Stock 345,678 just changed from $120 to $125"
  3. Both happening continuously and concurrently

Why prefix sums fail here:

  • Prefix sum array gives O(1) queries BUT requires O(n) for each update
  • With n = 1,000,000 and 5,000 updates/second = 5 billion operations/second! 💥
  • System would crash under the load

With Segment Tree:

  • Build: O(n) one-time setup
  • Each query: O(log n) ≈ 20 operations
  • Each update: O(log n) ≈ 20 operations
  • Total load: (10,000 × 20) + (5,000 × 20) = 300,000 operations/second ✓

The key: When you have frequent updates AND frequent queries on large data, Segment Tree's O(log n) for both operations becomes essential.

What Segment Tree Actually Does

Segment Tree is a binary tree that stores information about array segments. Each node represents a range and stores the result of an operation (like sum) for that range.

Think of it like organizing company departments:

  • Root node: "What's the total budget of the entire company?"
  • Internal nodes: "What's the total budget of this division?"
  • Leaf nodes: "What's the budget of this specific team?"

How the Operations Work

BUILD Operation - "Organize the segments hierarchically"

When you build a Segment Tree from array [100, 200, 150, 80]:

  1. Create leaf nodes for each element (representing ranges [0,0], [1,1], etc.)
  2. Each parent stores the sum of its children
  3. Root contains the sum of the entire array
  4. Tree structure enables efficient range queries
                [530]           <- Sum of [0,3]
               /      \
          [300]        [230]    <- Sums of [0,1] and [2,3]
          /   \        /   \
       [100] [200]  [150] [80]  <- Individual elements
        0     1      2     3    <- Array indices

QUERY Operation - "Get the sum of any range"

When you query range [1, 3]:

  1. Start at root and check if current range overlaps with query range
  2. If fully contained: return the stored sum
  3. If partial overlap: recursively check both children
  4. Combine results from overlapping segments

UPDATE Operation - "Change a value and maintain all sums"

When you update index 2 to 180:

  1. Update the leaf node for index 2
  2. Recursively update all ancestor nodes
  3. Each affected node recalculates its sum
  4. All range sums stay correct automatically

When These Operations Happen

These operations are called explicitly based on your needs:

const segTree = SegmentTree.build([100, 200, 150, 80], 0, 3);

// QUERY: Get sum of stocks from index 1 to 3
let portfolioValue = segTree.rangeQuery(1, 3); // Returns 430

// UPDATE: Stock at index 2 increased to 180
segTree.update(2, 180);

// QUERY: Get new sum after update
portfolioValue = segTree.rangeQuery(1, 3); // Returns 460

The beauty of Segment Tree is that once built, both queries and updates take O(log n) time regardless of the range size!

Single most important insight

Every range can be decomposed into O(log n) non-overlapping segments stored in the tree - and by recursively dividing ranges in half, we create a tree where any range query visits at most O(log n) nodes, achieving logarithmic time for both queries and updates.

Mental note: The algorithm's genius lies in precomputing results for specific "power-of-2-like" segments. At each level, we only need to decide: "Is this segment fully inside, fully outside, or partially overlapping my query range?" This simple decision at each node automatically combines the right segments to answer any range query efficiently.

Decision Framework

Segment Tree involves three key decisions:

During Build (divide and conquer):

  • Split range in half recursively
  • Create nodes bottom-up
  • Combine children's values for parent

During Query (range overlap check):

  • No overlap: Skip this subtree entirely
  • Complete overlap: Return this node's value directly
  • Partial overlap: Query both children and combine

During Update (propagate changes):

  • Update the leaf node
  • Recalculate parent as sum of children
  • Propagate up to root

Code

class SegmentTree {
  constructor(segmentSum, leftBoundary, rightBoundary) {
    // What this node stores
    this.sum = segmentSum;

    // Range this node represents [leftBoundary, rightBoundary] inclusive
    this.leftBoundary = leftBoundary;
    this.rightBoundary = rightBoundary;

    // Tree structure
    this.leftChild = null;
    this.rightChild = null;
  }

  // BUILD: Create tree from array - O(n) time
  static build(array, startIndex, endIndex) {
    const isSingleElement = startIndex === endIndex;

    // DECISION FRAMEWORK: Base case - leaf node for single element
    if (isSingleElement) {
      const elementValue = array[startIndex];
      return new SegmentTree(elementValue, startIndex, endIndex);
    }

    // DECISION FRAMEWORK: Divide range in half
    const midpoint = Math.floor((startIndex + endIndex) / 2);
    const leftHalfEnd = midpoint;
    const rightHalfStart = midpoint + 1;

    // Recursively build both halves
    const leftSubtree = SegmentTree.build(array, startIndex, leftHalfEnd);
    const rightSubtree = SegmentTree.build(array, rightHalfStart, endIndex);

    // DECISION FRAMEWORK: Combine - parent stores sum of children
    const combinedSum = leftSubtree.sum + rightSubtree.sum;
    const parentNode = new SegmentTree(combinedSum, startIndex, endIndex);

    // Connect the tree structure
    parentNode.leftChild = leftSubtree;
    parentNode.rightChild = rightSubtree;

    return parentNode;
  }

  // UPDATE: Change array[targetIndex] to newValue - O(log n) time
  update(targetIndex, newValue) {
    const isLeafNode = this.leftBoundary === this.rightBoundary;

    // DECISION FRAMEWORK: Found the target leaf
    if (isLeafNode) {
      this.sum = newValue;
      return;
    }

    // DECISION FRAMEWORK: Which child contains targetIndex?
    const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
    const targetIsInRightHalf = targetIndex > midpoint;

    if (targetIsInRightHalf) {
      this.rightChild.update(targetIndex, newValue);
    } else {
      this.leftChild.update(targetIndex, newValue);
    }

    // DECISION FRAMEWORK: Propagate change upward
    const updatedLeftSum = this.leftChild.sum;
    const updatedRightSum = this.rightChild.sum;
    this.sum = updatedLeftSum + updatedRightSum;
  }

  // QUERY: Get sum of range [queryStart, queryEnd] - O(log n) time
  rangeQuery(queryStart, queryEnd) {
    // Check how query range relates to this node's range
    const exactMatch =
      queryStart === this.leftBoundary && queryEnd === this.rightBoundary;

    // DECISION FRAMEWORK: Complete overlap - use precomputed sum
    if (exactMatch) {
      return this.sum;
    }

    // Find the split point of this node's range
    const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
    const leftHalfEnd = midpoint;
    const rightHalfStart = midpoint + 1;

    // DECISION FRAMEWORK: Determine overlap with children
    const queryIsEntirelyInRightHalf = queryStart >= rightHalfStart;
    const queryIsEntirelyInLeftHalf = queryEnd <= leftHalfEnd;

    if (queryIsEntirelyInRightHalf) {
      // Query only needs right subtree
      return this.rightChild.rangeQuery(queryStart, queryEnd);
    }

    if (queryIsEntirelyInLeftHalf) {
      // Query only needs left subtree
      return this.leftChild.rangeQuery(queryStart, queryEnd);
    }

    // DECISION FRAMEWORK: Query spans both children - split and combine
    const leftPortion = this.leftChild.rangeQuery(queryStart, leftHalfEnd);
    const rightPortion = this.rightChild.rangeQuery(rightHalfStart, queryEnd);
    const totalSum = leftPortion + rightPortion;

    return totalSum;
  }
}

// === EXAMPLE USAGE: Real-time Trading System ===
// Simulating a smaller version with 8 stocks for demonstration
const stockPrices = [100, 200, 150, 80, 250, 300, 175, 220];

// Build segment tree - O(n) one-time cost
console.log("Building Segment Tree for trading system...");
const tradingSystem = SegmentTree.build(stockPrices, 0, 7);

// Simulate rapid queries and updates happening concurrently
console.log("\n=== Simulating high-frequency trading activity ===");

// Multiple range queries from different users
console.log("\nUser queries (happening simultaneously):");
console.log(`Trader A - Portfolio [2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 805
console.log(`Trader B - Portfolio [0-3]: $${tradingSystem.rangeQuery(0, 3)}`); // 530
console.log(`Trader C - Portfolio [4-7]: $${tradingSystem.rangeQuery(4, 7)}`); // 945

// Market updates happening in real-time
console.log("\nMarket update: Stock 3 jumps from $80 to $120");
tradingSystem.update(3, 120);

// New queries immediately reflect the change
console.log("\nQueries after market change (instant reflection):");
console.log(`Trader A - Portfolio [2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 845
console.log(`Trader D - Portfolio [1-4]: $${tradingSystem.rangeQuery(1, 4)}`); // 690

// Another rapid update
console.log("\nMarket update: Stock 5 drops from $300 to $250");
tradingSystem.update(5, 250);

// More concurrent queries
console.log("\nMore user queries:");
console.log(
  `Trader E - Full portfolio [0-7]: $${tradingSystem.rangeQuery(0, 7)}`
); // 1545
console.log(
  `Trader F - High-value stocks [4-7]: $${tradingSystem.rangeQuery(4, 7)}`
); // 895

// The beauty: All these operations took O(log n) time each!
// With n = 1,000,000 in production, that's still only ~20 operations per query/update

Doubt buster

Common doubt: "Why not just keep a running sum array? If I maintain sums[i] = sum of elements 0 to i, I can answer any range query in O(1) time with sums[R] - sums[L-1]."

Why you might think prefix sums are better

A prefix sum array seems superior for range queries:

// Prefix sum approach
prefixSums = [0, 100, 300, 450, 530, 780, 1080];
// Query [2,5] = prefixSums[6] - prefixSums[2] = 1080 - 300 = 780
// O(1) query time - seems better than O(log n)!

This is absolutely true... IF you never need to update values. The prefix sum approach is perfect for static arrays with frequent queries.

Why prefix sums break down with updates

Here's where the problem emerges:

// Update index 2 from 150 to 180
// Now we need to update ALL prefix sums after index 2:
prefixSums[3] = 480 (was 450)
prefixSums[4] = 560 (was 530)
prefixSums[5] = 810 (was 780)
prefixSums[6] = 1110 (was 1080)
// This takes O(n) time for every update!

With frequent updates, prefix sums become a bottleneck. If you have m updates and q queries:

  • Prefix sums: O(n) per update × m updates = O(m·n) total
  • Segment Tree: O(log n) per update × m updates = O(m·log n) total

The key tradeoff

Use prefix sums when:

  • Array is static (no updates) or updates are rare
  • You need O(1) query time
  • Example: Computing cumulative statistics on historical data

Use Segment Tree when:

  • Both queries and updates are frequent
  • You can afford O(log n) for both operations
  • Example: Live dashboard showing real-time portfolio values

Concrete example showing the efficiency difference

Consider a trading system with 1 million stocks (n = 1,000,000):

Scenario: 10,000 queries and 10,000 updates per second

With prefix sums:

  • Each update: O(n) = 1,000,000 operations
  • 10,000 updates = 10 billion operations per second
  • System crashes! 💥

With Segment Tree:

  • Each update: O(log n) = ~20 operations
  • 10,000 updates = 200,000 operations per second
  • Each query: O(log n) = ~20 operations
  • 10,000 queries = 200,000 operations per second
  • Total: 400,000 operations per second - completely manageable! ✓

Why Segment Tree's structure enables fast updates

The magic is in how updates propagate:

To update index 2 in Segment Tree:
         [1110]  <- Update only this
        /      \
    [250]      [860]  <- Update only this
    /   \      /    \
 [100] [150] [180] [80]  <- Update only this
               ↑
          Changed value

Only O(log n) nodes need updating - one per tree level!

Compare this to prefix sums where EVERY subsequent sum needs updating. The tree structure limits the "damage radius" of any update to just the path from leaf to root.

The bottom line

Segment Tree trades slightly slower queries (O(log n) vs O(1)) for dramatically faster updates (O(log n) vs O(n)). When your data changes frequently, this tradeoff is essential. The logarithmic guarantee for BOTH operations makes Segment Tree the go-to choice for dynamic range query problems.

← Back to Blog