Segment Tree (Range Query)
Learn Segment Tree (Range Query) (Range Query Techniques, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Segment Tree: Range Queries with Point Updates A segment tree stores the answer for every block of the array in a binary tree: leaves are single elements, and each parent combines its two children. A point update changes one leaf and the log n ancestors above it; a range query combines at most about 2 log n blocks. Both cost O(log n) , so it handles arrays that change. The compact bottom-up version stores the tree in an array of size 2n .