Is Range Sum Query - Mutable easy or hard?

The problem is rated Medium because it requires designing a data structure rather than writing a simple algorithm. Understanding Segment Trees or Fenwick Trees is necessary to reach the optimal O(log n) solution.

Range Sum Query - Mutable Python/Java solution

Typical implementations build a Segment Tree class with update and query methods. Python and Java solutions both maintain a tree array where each node stores the sum of a segment, allowing O(log n) updates and queries.

How to solve Range Sum Query - Mutable in O(log n)?

Use a Segment Tree or Binary Indexed Tree. Store prefix or segment sums in a tree structure so updates propagate through log n nodes. Range queries combine partial sums from relevant nodes, giving O(log n) complexity.

What is the best approach for Range Sum Query - Mutable?

Segment Tree is the most common optimal solution. It supports both update and range sum queries in O(log n) time. The tree stores sums of segments so queries combine only relevant nodes instead of scanning the array.

Is Range Sum Query - Mutable asked at Google/Amazon/Meta?

Range query data structure problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variations involving Segment Trees or Fenwick Trees are common in system design style coding rounds.

What data structure is used in Range Sum Query - Mutable?

Segment Tree and Binary Indexed Tree (Fenwick Tree) are the main data structures. Both maintain partial sums that allow fast updates and range queries without recomputing sums from scratch.

What is the time complexity of Range Sum Query - Mutable?

Using a Segment Tree, both update(index, val) and sumRange(left, right) run in O(log n) time. Building the tree initially takes O(n). The brute force array method has O(1) updates but O(n) query time.

Description Solution Video 26:32

307. Range Sum Query - Mutable

Medium43.9% acceptance4 companies

Given an integer array nums, handle multiple queries of the following types:

Update the value of an element in nums.
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.
void update(int index, int val) Updates the value of nums[index] to be val.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Constraints: