Segment Tree for Range Queries

Concepts: pySegmentTree, pyRangeQuery, pyPointUpdate

A segment tree is a binary tree built over an array where each node stores an aggregate (sum, min, max) for a contiguous range of the array. The leaves are the individual elements. Internal nodes aggregate their children. This structure supports both range queries (what is the sum of elements 3 to 7?) and point updates (update element 5 to a new value) in O(log n) time. The critical advantage over a prefix sum array: prefix sums are O(1) for queries but O(n) for updates. Segment trees are O(log n) for both — they are designed for arrays that change. Array-Based Segment Tree