Segment Tree Complete Guide

Data Structure • extra hard

Segment tree supports efficient range queries with point/range updates.

It recursively partitions array intervals and stores aggregate values at internal nodes.

Use it when repeated query+update operations must both remain fast.

Typical Complexity Baseline

Metric	Value
Query/update	`O(log n)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Segment tree aggregate over ranges

Each internal node aggregates its two children. A range query touches O(log n) nodes.

Step 1/8Range query: sum over [2..5]. Each node covers an index range.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Segment Tree Data Structure - Min Max Queries

Channel: Stable Sort

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Tree node range

What it is Interval [left,right] represented by node.

Why it matters Tree node range is a required building block for understanding how Segment Tree stays correct and performant on large inputs.

Aggregate value

What it is Precomputed query answer for interval.

Why it matters Aggregate value is a required building block for understanding how Segment Tree stays correct and performant on large inputs.

Build

What it is Construct tree bottom-up from source array.

Why it matters Build is a required building block for understanding how Segment Tree stays correct and performant on large inputs.

Query

What it is Combine only overlapping intervals.

Why it matters Query is a required building block for understanding how Segment Tree stays correct and performant on large inputs.

Update

What it is Update path from leaf to root after value change.

Why it matters Update is a required building block for understanding how Segment Tree stays correct and performant on large inputs.

Range query

What it is Ask aggregate over interval [l, r].

Why it matters Ask aggregate over interval [l, r]. In Segment Tree, this definition helps you reason about correctness and complexity when inputs scale.

Point update

What it is Change one index value and refresh affected nodes.

Why it matters Change one index value and refresh affected nodes. In Segment Tree, this definition helps you reason about correctness and complexity when inputs scale.

Lazy propagation

What it is Delay range updates until needed for faster bulk operations.

Why it matters Delay range updates until needed for faster bulk operations. In Segment Tree, this definition helps you reason about correctness and complexity when inputs scale.

Associative operation

What it is Operation where grouping does not change result.

Why it matters Operation where grouping does not change result. In Segment Tree, this definition helps you reason about correctness and complexity when inputs scale.

Fenwick tree

What it is Alternative structure for some prefix/range operations.

Why it matters Alternative structure for some prefix/range operations. In Segment Tree, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/8

Range query: sum over [2..5]. Each node covers an index range.

Step 2/8

Visit [0..7]. Query [2..5] partially overlaps → recurse into children.

Step 3/8

Visit [0..3]. Partial overlap with [2..5] → recurse.

Step 4/8

[0..1] disjoint from [2..5] → skip.

Step 5/8

[2..3] fully inside [2..5] → take this node's aggregate. Stop.

Step 6/8

Visit [4..7]. Partial overlap → recurse.

Step 7/8

[4..5] fully inside → take.

Step 8/8

[6..7] disjoint → skip. Done. Two takes covered the query in O(log n).

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Prefix sums

Choose this when Choose segment tree when updates happen frequently.

Tradeoff Prefix sums are simpler and faster for static arrays.

vs. Fenwick tree

Choose this when Choose segment tree for broader query operation flexibility.

Tradeoff Fenwick is simpler and often lighter for prefix sums.

vs. Brute-force range scan

Choose this when Choose segment tree for heavy query/update workloads.

Tradeoff Brute force may be fine for tiny datasets.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Trading/finance dashboards

High-frequency metric dashboards require many range aggregates with incoming updates.

Takeaway Segment trees provide predictable low-latency updates + queries.

Telemetry platforms

Time-bucket range aggregation can leverage tree-based interval summaries.

Takeaway Hierarchical aggregation supports interactive exploration speed.

Gaming analytics

Live score and event windows need rapid interval stats under continuous updates.

Takeaway Range structures reduce expensive full rescans.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Store interval sums in tree array; query and update in logarithmic time.

Complexity: Build O(n), Query O(log n), Update O(log n)

Range sum segment tree (point update)

Language

class RangeSumSegmentTree {
  private readonly sourceValues: number[]
  private readonly treeValues: number[]

  constructor(sourceValues: number[]) {
    this.sourceValues = [...sourceValues]
    this.treeValues = new Array<number>(sourceValues.length * 4).fill(0)
    if (sourceValues.length > 0) {
      this.buildTree({ nodeIndex: 1, leftIndex: 0, rightIndex: sourceValues.length - 1 })
    }
  }

  queryRange(params: { queryLeftIndex: number; queryRightIndex: number }): number {
    if (this.sourceValues.length === 0) return 0
    return this.queryTree({ nodeIndex: 1, leftIndex: 0, rightIndex: this.sourceValues.length - 1, queryLeftIndex: params.queryLeftIndex, queryRightIndex: params.queryRightIndex })
  }

  updateValue(params: { updateIndex: number; nextValue: number }): void {
    if (this.sourceValues.length === 0) return
    this.updateTree({ nodeIndex: 1, leftIndex: 0, rightIndex: this.sourceValues.length - 1, updateIndex: params.updateIndex, nextValue: params.nextValue })
  }

  private buildTree(params: { nodeIndex: number; leftIndex: number; rightIndex: number }): void {
    if (params.leftIndex === params.rightIndex) {
      this.treeValues[params.nodeIndex] = this.sourceValues[params.leftIndex]
      return
    }

    const middleIndex = Math.floor((params.leftIndex + params.rightIndex) / 2)
    this.buildTree({ nodeIndex: params.nodeIndex * 2, leftIndex: params.leftIndex, rightIndex: middleIndex })
    this.buildTree({ nodeIndex: params.nodeIndex * 2 + 1, leftIndex: middleIndex + 1, rightIndex: params.rightIndex })
    this.treeValues[params.nodeIndex] = this.treeValues[params.nodeIndex * 2] + this.treeValues[params.nodeIndex * 2 + 1]
  }

  private queryTree(params: { nodeIndex: number; leftIndex: number; rightIndex: number; queryLeftIndex: number; queryRightIndex: number }): number {
    if (params.queryRightIndex < params.leftIndex || params.rightIndex < params.queryLeftIndex) return 0
    if (params.queryLeftIndex <= params.leftIndex && params.rightIndex <= params.queryRightIndex) return this.treeValues[params.nodeIndex]

    const middleIndex = Math.floor((params.leftIndex + params.rightIndex) / 2)
    const leftSum = this.queryTree({ nodeIndex: params.nodeIndex * 2, leftIndex: params.leftIndex, rightIndex: middleIndex, queryLeftIndex: params.queryLeftIndex, queryRightIndex: params.queryRightIndex })
    const rightSum = this.queryTree({ nodeIndex: params.nodeIndex * 2 + 1, leftIndex: middleIndex + 1, rightIndex: params.rightIndex, queryLeftIndex: params.queryLeftIndex, queryRightIndex: params.queryRightIndex })
    return leftSum + rightSum
  }

  private updateTree(params: { nodeIndex: number; leftIndex: number; rightIndex: number; updateIndex: number; nextValue: number }): void {
    if (params.leftIndex === params.rightIndex) {
      this.sourceValues[params.updateIndex] = params.nextValue
      this.treeValues[params.nodeIndex] = params.nextValue
      return
    }

    const middleIndex = Math.floor((params.leftIndex + params.rightIndex) / 2)
    if (params.updateIndex <= middleIndex) {
      this.updateTree({ nodeIndex: params.nodeIndex * 2, leftIndex: params.leftIndex, rightIndex: middleIndex, updateIndex: params.updateIndex, nextValue: params.nextValue })
    } else {
      this.updateTree({ nodeIndex: params.nodeIndex * 2 + 1, leftIndex: middleIndex + 1, rightIndex: params.rightIndex, updateIndex: params.updateIndex, nextValue: params.nextValue })
    }

    this.treeValues[params.nodeIndex] = this.treeValues[params.nodeIndex * 2] + this.treeValues[params.nodeIndex * 2 + 1]
  }
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Incorrect overlap logic in query recursion.
Off-by-one errors in interval boundaries.
Insufficient tree size allocation.
Forgetting to propagate updates up the tree.
Implementing lazy propagation incorrectly and corrupting results.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Use segment tree when range queries and point/range updates both matter.
Write overlap cases explicitly: no overlap, partial overlap, full overlap.
Indexing bugs are common; keep a consistent interval convention (inclusive bounds).
If range updates are frequent, learn lazy propagation early.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Range sum/min/max queries in O(log n).
Point updates in O(log n) while keeping query performance stable.
Generalizable to many associative operations.

LeetCode-specific tips (pattern-identification signals)

Identification signal: many range queries plus point/range updates on the same array.
Identification signal: brute force per query is too slow under high query count constraints.
If prompt mixes "update" and "query [l, r]" repeatedly, segment tree (or Fenwick) should be considered.
For Segment Tree questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Range Sum Query - Mutable	Medium	`O(log n)`
2	Range Sum Query 2D - Mutable	Hard	`O(log n * log m)`
3	Count of Smaller Numbers After Self	Hard	`O(n log n)`
4	My Calendar III	Hard	`O(n log n)`
5	Falling Squares	Hard	`O(n log n)`
6	Range Module	Hard	`O(log n)`
7	Longest Increasing Subsequence II	Hard	`O(n log n)`
8	Count Integers in Intervals	Hard	`O(log n)`
9	Rectangle Area II	Hard	Sweep + segment tree
10	Maximum Sum Queries	Hard	`O(n log n)`