Implement a Segment Tree (Range Query)

A Segment Tree is a binary tree structure designed to answer range queries efficiently, particularly when the underlying array undergoes frequent changes. Each node in the tree represents an interval; leaf nodes correspond to single array elements, while internal nodes store the aggregate result of their children, such as the sum or minimum value. For an array of size n, we typically implement this using an array of size 4n to ensure sufficient space for all nodes. To build the tree, I use a recursive function. If the current range has only one element, I assign it to the leaf node. Otherwise, I split the range into two halves, recursively build the left and right subtrees, and then combine their results to populate the current node. For example, if computing sums, the parent node equals the sum of its left and right children. For the query operation, given a range [L, R], I start at the root. If the current node's range is completely outside [L, R], I return a neutral value like zero. If it is completely inside, I return the stored value. If there is partial overlap, I recursively query both children and combine the results. This ensures we visit only O(log n) nodes rather than scanning the entire array. In an Oracle context, this approach significantly reduces latency for analytics queries on large datasets compared to linear scans.