Data Structure • extra-hard

Segment Tree Complete Guide

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)`

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Segment Tree Data Structure - Min Max Queries

Channel: Stable Sort

Full video link:

https://www.youtube.com/watch?v=xztU7lmDLv8

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

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.

Putting It All Together

This walkthrough connects the core concepts of Segment Tree into one end-to-end execution flow.

Step 1

Tree node range

Interval [left,right] represented by node.

Before

Array

21534

Need fast range sums with updates

→

After

Root holds sum(0..4)=15
Tree built in O(n)

Transition

Build tree nodes for segments

→Store aggregate at each node

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

Step 2

Aggregate value

Precomputed query answer for interval.

Before

Query range

Traverse from root

→

After

Result sum(1..3)=9
Query cost O(log n)

Transition

Skip non-overlapping segments

→Combine fully covered segment values

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

Step 3

Build

Construct tree bottom-up from source array.

Before

Point update index 2 -> value 6
Leaf and ancestors need refresh

→

After

Root sum updated to 16
Tree remains consistent

Transition

Update leaf segment [2,2]

→Recompute parent aggregates upward

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

Step 4

Query

Combine only overlapping intervals.

Before

Query range

after update
All nodes already synchronized

→

After

Result = 16
Both query and update remain O(log n)

Transition

Visit minimal required nodes

→Aggregate quickly

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

How It Compares

vs Prefix sums

When to choose this: Choose segment tree when updates happen frequently.

Tradeoff: Prefix sums are simpler and faster for static arrays.

vs Fenwick tree

When to choose this: Choose segment tree for broader query operation flexibility.

Tradeoff: Fenwick is simpler and often lighter for prefix sums.

vs Brute-force range scan

When to choose this: Choose segment tree for heavy query/update workloads.

Tradeoff: Brute force may be fine for tiny datasets.

Real-World Stories and Company Examples

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.

Implementation Guide

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

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

Language

Range sum segment tree (point update)

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]
  }
}

Common Problems and Failure Modes

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.

Tips and Tricks

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.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.

LeetCode Progression (Easy to Hard)

Back to DSA Guide Catalog

#	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)`