307. Range Sum Query - Mutable

Problem Description

The problem presents a scenario where we have an initial array of integers, nums, and we want to do two main types of operations:

1. Update: Change the value of an element in the array at a given index to a new value.
2. Sum Range: Calculate the sum of a consecutive range of elements in the array, specified by a starting index left and an ending index right.

We need to design a NumArray class that has:

• A constructor that takes an array of integers nums and initializes the object.
• An update method that accepts the index of the element to update and the new value that will replace the current value at that index.
• A sumRange method that returns the sum of the elements in the range between left and right indices, inclusive.

This problem is a classic example of the need for efficient algorithms to handle dynamic data—data that can change over time—especially when we have to perform frequent update and query operations.

Intuition

For solving the problem efficiently, we resort to advanced data structures like Binary Indexed Trees (BITs) or Segment Trees because they are well-suited for handling dynamic datasets where elements can change, and we need to calculate range sums quickly.

With a regular array or list, updating an element is easy and quick (O(1) time complexity), but calculating the sum of a range requires iterating over all the elements in that range (O(n) time complexity where n is the range size). This is inefficient if we have many sum queries.

The intuition behind using a Binary Indexed Tree (BIT), also known as a Fenwick Tree, in this solution is that a BIT allows us to:

• Update the value of an element in logarithmic time complexity (O(log n)).
• Calculate the prefix sum (sum from start to the given index) also in logarithmic time (O(log n)).
• By having the ability to calculate prefix sums efficiently, we can find the sum of any given range by calculating the difference between two prefix sums.

A BIT achieves this by maintaining a tree-like array structure where each node contains the sum of a range of elements from the original array. It uses clever index manipulation to update and calculate sums efficiently.

The update method in the BIT adds the difference between the new value and the current value at the specified index, which will affect all the following nodes in the tree that includes this index in their range.

The sumRange method uses the BIT to compute the prefix sum up to right + 1, and then subtracts the prefix sum up to left to get the sum of the range from left to right.

By incorporating BIT into the NumArray class, we can efficiently handle multiple updates and sum range queries satisfying the problem requirements.

Learn more about Segment Tree patterns.

Solution Approach

The provided solution uses a Binary Indexed Tree (BIT), which is an efficient data structure for maintaining the prefix sums of a dynamic array, to implement the NumArray class. The key functions of the BIT are update and query, which allow for updating an element and calculating prefix sums, respectively.

Binary Indexed Tree (BIT)

A BIT is built on an array c[], where each element at index x keeps the cumulative sum of a specific range of elements from the original array. The size of the range depends on the last set bit (LSB) in the index of the tree's array: lowbit(x) = x & -x.

• The lowbit function determines the decimal value of the least significant bit that is set to 1. This helps in determining the size of the ranges represented by the nodes in BIT.

• The ranges are formed such that each range covers indices from x - lowbit(x) + 1 to x, inclusive.

BIT Construction

During the initialization of the NumArray class, a new BIT is created with the size equal to the number of elements in nums. Then, an update operation is performed on the BIT for each element in the nums array to populate the tree.

BIT Update Operation

The update operation (BinaryIndexedTree.update) applies a delta (the change in value) to the element at a given index x. Since changing the value of an element affects all prefix sums that include this element, subsequent elements in the BIT need to be updated. We propagate this change up the tree structure by adding delta to all necessary elements in the BIT array, moving upward by adding lowbit(x) to the index x, up to the size of the BIT.

For NumArray.update, we first calculate the original value using the sumRange method and then apply the actual update as val - prev to ensure we're updating with the correct delta.

BIT Query Operation

The query operation (BinaryIndexedTree.query) calculates the prefix sum up to a given index x. This is achieved by starting at the specified index and moving downwards towards the root of the BIT, adding values from the tree's array corresponding to each range covered. To find which element in the tree to move to next, we subtract lowbit from x, repeating this until x becomes 0.

For NumArray.sumRange, we use BIT's query function to get the prefix sum up to right + 1 and subtract from it the prefix sum up to left. This effectively gives us the sum of elements from nums[left] to nums[right].

In summary, by using BIT, we can support both update and range sum operations efficiently, with both operations running in O(log n) time complexity, where n is the number of elements in the array nums. The BIT data structure uses a clever method of index manipulation to ensure that these operations remain efficient even as the values in the array change.

Example Walkthrough

Let's demonstrate the solution approach using a small example with the following initial array nums: [1, 3, 5]. We want to execute several update and sumRange operations on the NumArray class that internally uses a Binary Indexed Tree (BIT).

1. Initialization

   We initialize the NumArray class with the array nums. During initialization, the BIT is constructed for the given array. The BIT, let's call it c, would be initiated and populated such that it can efficiently calculate prefix sums up to any index.

2. Populating the BIT

   For our array [1, 3, 5], we would perform an update operation in the BIT for each of the elements:

   • update(1, 1) for the first element (1 at index 0).
   • update(2, 3) for the second element (3 at index 1).
   • update(3, 5) for the third element (5 at index 2).

   After this, our BIT might represent cumulative sums like this:

   1c[1] = 1     // nums[0]
   2c[2] = 4     // nums[0] + nums[1]
   3c[3] = 5     // nums[2]
   4c[4] = 9     // nums[0] + nums[1] + nums[2]

   Note: The indices in a BIT are typically 1-based.

3. Solving sumRange Query

   If we want to calculate the sum range for left = 0 and right = 2, the BIT would calculate the sum with:

   1sum(3) - sum(0) = (nums[0] + nums[1] + nums[2]) - 0 = 9

   So sumRange(0, 2) returns 9, which is indeed the sum of [1, 3, 5].

4. Performing an update Operation

   Now, let's say we want to update the value at index 1 (second element) from 3 to 2. We determine the difference to update in the BIT, which is -1 (new value 2 minus old value 3), and propagate this delta through the relevant cells in the BIT:

   1old BIT: c[1] = 1, c[2] = 4, c[3] = 5, c[4] = 9
   2update the BIT: c[2] = c[2] - 1, c[4] = c[4] - 1
   3new BIT: c[1] = 1, c[2] = 3, c[3] = 5, c[4] = 8

5. New sumRange Query Post Update

   Now, if we calculate sumRange(0, 2) again, we have:

   1sum(3) - sum(0) = (nums[0] + updated nums[1] + nums[2]) - 0 = 8

   With the new values, the sumRange(0, 2) returns 8, showing that our updated array [1, 2, 5] has been properly accounted for in the BIT.

Through these operations, we can see that the BIT provides an efficient means to handle multiple updates and range sum queries, with both the update and sumRange operations running in O(log n) time complexity, which is a significant improvement over naive approaches.

Solution Implementation

Time and Space Complexity

The code defines a BinaryIndexedTree class, which is commonly called a Fenwick Tree, that provides efficient methods to compute prefix sums and update single elements in an array.

Constructor of BinaryIndexedTree:

• The constructor initializes an array self.c with n + 1 zeros, where n is the length of the input list. The time and space complexity are both O(n).

update Method:

• This method has a while loop that runs as long as x <= self.n. On each iteration, x is incremented by the lowest set bit (result of lowbit(x)). The time complexity is O(log n) because in the worst case, the loop does log2(n) iterations.

query Method:

• This method is similar to update but works in reverse, subtracting the lowest set bit on each iteration. The time complexity is also O(log n) for the same reasons.

Constructor of NumArray:

• This constructor initializes a BinaryIndexedTree and updates it with the initial nums array. Initializing the Fenwick Tree takes O(n), while the loop does a pass through nums array, calling update for each element. Since each update call takes O(log n), initializing the Fenwick Tree with n elements becomes an O(n log n) operation for the constructor.

update Method of NumArray:

• This method calculates the difference between the new value and the current value at index and updates the Fenwick Tree accordingly by calling the tree's update method once. Since tree.update has a time complexity of O(log n), the update method in NumArray also has a time complexity of O(log n).

sumRange Method:

• This method calls query twice and returns their difference to get the sum of the range. Because each query call has a time complexity of O(log n), the overall time complexity of sumRange is O(log n).

The space complexity of the NumArray class is O(n) because it stores a Fenwick Tree of size n.

In summary:

• Time Complexity:
  • BinaryIndexedTree constructor: O(n)
  • update: O(log n)
  • query: O(log n)
  • NumArray constructor: O(n log n)
  • NumArray update: O(log n)
  • NumArray sumRange: O(log n)
• Space Complexity:
  • For both BinaryIndexedTree and NumArray: O(n)

Learn more about how to find time and space complexity quickly using problem constraints.