Interview OS
Back to Algorithms & Data Structures

Library

Segment / Fenwick trees

O(log n) range queries + updates.

Range

Overview

A segment tree answers range queries (sum, min, max) and point/range updates in O(log n) over an array. It's the structure to know when you need repeated aggregate queries on mutating data.

How it works

Range
BuildQueryUpdateOutputRange treeO(n)Range opO(log n)Point/lazyO(log n)Use
DataServiceEdgeClient

Step by step, with examples

  1. 1

    Range tree

    • Each node covers a sub-range.
  2. 2

    Range op

    • Sum/min over [l, r].
  3. 3

    Point/lazy

    • Modify a leaf and propagate.
  4. 4

    Use

    • Fast range aggregates.
    • Example: Fenwick = BIT

Overview

Segment trees answer range queries (sum/min/max) with point or range updates in O(log n).

When to use it

  • Range-sum with updates
  • Range-min queries
  • Counting inversions (BIT)

Common pitfalls

  • Off-by-one in ranges
  • Forgetting lazy propagation for range updates

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides