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.