Expert · Module 26 · Lesson 2 of 4
Segment trees
A binary tree of partial answers over the array: build in linear time, update a point and answer a range in logarithmic time, merging with any associative operation instead of only sums.
By the end you can
- Compute a node's child and parent indices from the array layout, and say how many cells it needs
- Trace a range query and count the disjoint nodes that enter the answer
- Predict which node values a point update rewrites, and explain when a Fenwick tree would do instead
Builds on Sparse tables, The heap property in an array.
01 · A question first
Prefix sums go stale the moment you write to the array, and rebuilding one costs O(n). You want range sums and single-element updates interleaved, plus the same answers for minimums. A tree of partial summaries gives O(log n) for both, stored in a plain array where each node's children sit at fixed offsets.
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- When answers must survive changes
- The tree over the array
- Children at 2i and 2i+1
- A query stops at full coverage
- Updates and the build
- Segment tree or Fenwick tree
- Where it is used
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem