Sign in to watch this lesson
Algorithms - Trees and Range Queries · 5:39
Segment Tree
A segment tree gives every half of every half of an array its own vertex, so any range is answered by a handful of stored results. We build one on a small array, run a range-sum query through its three cases, update one element, prove that a query visits at most four vertices per level, store the tree in a 4n array or the compact bottom-up layout, and measure it against a plain loop and a Fenwick tree.
You will learn
- Build a sum segment tree in O(n) with the heap layout (root 1, children 2v and 2v + 1)
- Answer a range query with the three cases (no overlap, full containment, partial) and explain why at most four vertices per level are visited
- Apply a point update in O(log n) by recomputing one vertex per level
- Implement the bottom-up iterative variant and choose between a segment tree and a Fenwick tree