Range Sum Query - Mutable

Medium· Fenwick tree· segment tree

Problem

Design a structure over an integer array that supports two operations: overwrite the value at an index, and return the sum of a contiguous index range. Both operations may be called many times, interleaved.

Examples

Input: nums = [1,3,5]; sumRange(0,2); update(1,2); sumRange(0,2)

Output: [9, 8]

After setting index 1 to 2 the array is [1,2,5].

Constraints

• 1 <= nums.length <= 3·10^4
• At most 3·10^4 calls to update and sumRange

Hints & approach

Hint 1

A plain prefix-sum array makes updates O(n); a plain array makes queries O(n).

Hint 2

You want a structure where both operations touch only O(log n) stored sums.

Hint 3

A Fenwick tree stores partial sums at indices determined by the lowest set bit.

Approachtry the hints first

Build a Fenwick tree (binary indexed tree) of size n + 1. To add delta at index i, walk i += i & -i updating each node; to get a prefix sum up to i, walk i -= i & -i accumulating. An update applies the difference between the new and old value, and sumRange(l, r) is prefix(r) - prefix(l - 1). A segment tree storing interval sums works equally well.

Time O(log n) per operation · Space O(n)

Next →Count of Smaller Numbers After Self