Range Sum Query - Mutable - Solution & Explanation

Problem Overview: You need to design a data structure that supports two operations on an integer array: update the value at a specific index and return the sum of elements within a range [left, right]. The challenge comes from handling frequent updates efficiently while still answering range queries quickly.

Approach 1: Brute Force - Simple Array Modification (Update O(1), Query O(n))

The simplest design stores the numbers directly in an array. When update(index, val) is called, you replace the value at that index in O(1) time. For sumRange(left, right), iterate from left to right and accumulate the sum. This approach works because array access is constant time, but every query requires scanning part of the array. Time complexity becomes O(n) per query and O(1) per update, with O(n) space for the array. It works for small inputs or when queries are rare, but it becomes slow when many range queries are executed.

Approach 2: Segment Tree (Update O(log n), Query O(log n))

A segment tree stores aggregated sums of subranges in a binary tree structure. Each node represents the sum of a segment of the array, and its children represent smaller segments. Building the tree takes O(n) time. When you update a value, the change propagates from the leaf node up to the root, updating all affected segment sums in O(log n) time. For sumRange(left, right), the query walks the tree and combines sums from nodes that fully cover parts of the requested range, also in O(log n) time.

This structure avoids scanning the array repeatedly. Instead of recalculating sums from scratch, it reuses precomputed segment sums. Segment trees are ideal when the array is frequently modified and queries are frequent. They provide a balanced tradeoff: logarithmic time for both operations and O(n) memory.

Another common alternative is a Binary Indexed Tree (Fenwick Tree), which also supports prefix sums and updates in O(log n). Many engineers prefer it for simpler implementation, but segment trees provide more flexibility for advanced range operations. Both approaches rely on understanding prefix aggregation over an array.

Recommended for interviews: Start by explaining the brute force array solution to show baseline reasoning. Then move to the segment tree optimization. Interviewers expect a logarithmic-time data structure because the problem mixes updates and range queries. Demonstrating how updates propagate through the tree and how queries combine partial segments shows strong understanding of range query data structures.