Skip to main content

Segment Tree

Learn Segment Tree (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

O(log n) Range Queries AND Point Updates A Segment Tree is a binary tree where each node covers a RANGE of the array; leaves are single elements, and internal nodes combine their two children's ranges. Both range queries (sum, min, max over [l,r]) and point updates run in O(log n) - beating a plain array's O(n) range query or a prefix-sum array's O(n) update.

More lessons in Advanced Data Structures