Segment Tree Range Queries

Problem Support range aggregate queries — range sum, or range min/max — together with point or range updates over an array, both efficiently and interleaved arbitrarily.

Input / Output

• Input: an initial array of n integers, followed by a mix of query(l, r) and update(...) operations.
• Output: the aggregate over [l, r] for each query.

Constraints

• Array size and number of operations both up to 10^5, which rules out O(n) per query.
• Queries and updates interleave, so precomputing a prefix-sum array is not sufficient — every update would cost O(n) to rebuild.

Example

• Array [1,3,5,7,9,11]: sum(1,3) = 3+5+7 = 15. Then update(index 2, value 10) → sum(1,3) = 3+10+7 = 20.
• Tricky case: a query spanning the whole array, or a single-element range l == r, must both work without special-casing.