Segment Trees

If a BIT handles sums, a segment tree handles everything — sums, minimums, maximums, GCDs, and any associative operation. It's the most versatile range query structure you'll encounter. This post breaks down what segment trees are, how they work under the hood, and why they're the go-to when a BIT or prefix sum isn't flexible enough.

What is a segment tree?

A segment tree is a binary tree built on top of an array where each node stores an aggregate value (sum, min, max, etc.) for a range of the array. The root covers the entire array. Its children cover the left and right halves. The leaves are individual elements.