307. Range Sum Query - Mutable

MediumDesignBinary Indexed TreeSegment TreeArray
Leetcode Link

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

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

1class BinaryIndexedTree:
2    def __init__(self, size):
3        self.size = size
4        self.tree_array = [0] * (size + 1)
5
6    @staticmethod
7    def lowbit(index):
8        """Returns the last significant bit of the index."""
9        return index & -index
10
11    def update(self, index, delta):
12        """
13        Updates the Binary Indexed Tree (BIT) by adding 'delta' to the element at 'index'.
14        """
15        while index <= self.size:
16            self.tree_array[index] += delta
17            index += BinaryIndexedTree.lowbit(index)
18
19    def query(self, index):
20        """
21        Queries the sum of the elements up to 'index'.
22        """
23        total_sum = 0
24        while index > 0:
25            total_sum += self.tree_array[index]
26            index -= BinaryIndexedTree.lowbit(index)
27        return total_sum
28
29
30class NumArray:
31    def __init__(self, nums):
32        """
33        Initializes the NumArray object with the integer array 'nums'.
34        """
35        self.binary_indexed_tree = BinaryIndexedTree(len(nums))
36        for i, value in enumerate(nums, start=1):
37            self.binary_indexed_tree.update(i, value)
38
39    def update(self, index, val):
40        """
41        Updates the value of 'nums' at 'index' to be 'val'.
42        """
43        current_value = self.sumRange(index, index)
44        self.binary_indexed_tree.update(index + 1, val - current_value)
45
46    def sumRange(self, left, right):
47        """
48        Returns the sum of elements from 'left' to 'right' (inclusive).
49        """
50        return self.binary_indexed_tree.query(right + 1) - self.binary_indexed_tree.query(left)
51
52
53# The NumArray object can be used as follows:
54# numArray = NumArray(nums)
55# numArray.update(index, val)
56# sum = numArray.sumRange(left, right)
57
1// Binary Indexed Tree (Fenwick Tree) to maintain prefix sums
2class BinaryIndexedTree {
3    private int size; // size of array that Binary Indexed Tree maintains
4    private int[] tree; // internal representation of Binary Indexed Tree
5
6    // Constructor initializes the tree with the given size
7    public BinaryIndexedTree(int size) {
8        this.size = size;
9        this.tree = new int[size + 1]; // +1 because indexing starts from 1
10    }
11
12    // Updates the tree with the provided value `delta` at index `x`
13    public void update(int x, int delta) {
14        while (x <= size) {
15            tree[x] += delta; // update current index
16            x += lowbit(x); // move to the next index to update
17        }
18    }
19
20    // Query the sum of the array up to index `x`
21    public int query(int x) {
22        int sum = 0;
23        while (x > 0) {
24            sum += tree[x]; // add current index value to sum
25            x -= lowbit(x); // move to previous index to continue the sum
26        }
27        return sum;
28    }
29
30    // Helper method to calculate lowest one bit (rightmost) of `x`
31    private static int lowbit(int x) {
32        return x & -x; // isolates the lowest one bit
33    }
34}
35
36// Class to support range sum queries and updates
37class NumArray {
38    private BinaryIndexedTree binaryIndexedTree;
39
40    // Constructor builds a Binary Indexed Tree using provided input array
41    public NumArray(int[] nums) {
42        binaryIndexedTree = new BinaryIndexedTree(nums.length);
43        for (int i = 0; i < nums.length; ++i) {
44            binaryIndexedTree.update(i + 1, nums[i]); // populate Binary Indexed Tree with initial values
45        }
46    }
47
48    // Updates the value at the given index with the new value `val`
49    public void update(int index, int val) {
50        int currentValue = sumRange(index, index); // get current value at the index
51        binaryIndexedTree.update(index + 1, val - currentValue); // apply the difference
52    }
53
54    // Computes the sum of the elements within the range [left, right]
55    public int sumRange(int left, int right) {
56        // Get the prefix sum up to 'right' and subtract the sum up to 'left'
57        // to obtain the sum of range [left, right]
58        return binaryIndexedTree.query(right + 1) - binaryIndexedTree.query(left);
59    }
60}
61
62// Usage:
63// NumArray numArray = new NumArray(intArray);
64// numArray.update(index, newValue);
65// int sum = numArray.sumRange(left, right);
66
1#include <vector>
2using namespace std;
3
4// Class to represent a Binary Indexed Tree (or Fenwick Tree),
5// which allows efficient queries and updates of prefix sums.
6class BinaryIndexedTree {
7public:
8    int size;               // The size of the array
9    vector<int> treeArray;  // The array that represents the tree
10
11    // Constructor to initialize the tree with a given size.
12    BinaryIndexedTree(int size)
13        : size(size)
14        , treeArray(size + 1, 0) {}  // Allocate space for 'size+1' because of 1-based indexing
15
16    // Function to update the value at a specific index,
17    // 'delta' represents the value to be added.
18    void update(int index, int delta) {
19        while (index <= size) {
20            treeArray[index] += delta;  // Add 'delta' to current index
21            index += lowbit(index);     // Move to the next index that needs to be updated
22        }
23    }
24
25    // Function to return the prefix sum from the tree, up to a given index.
26    int query(int index) {
27        int sum = 0;
28        while (index > 0) {
29            sum += treeArray[index]; // Add current value to the sum
30            index -= lowbit(index);  // Move to the next component of the prefix sum
31        }
32        return sum;
33    }
34
35private:
36    // Internal function to calculate the least significant bit that is set.
37    int lowbit(int x) {
38        return x & -x;
39    }
40};
41
42// NumArray class to manage an array of numbers using a Binary Indexed Tree,
43// enabling efficient updates and range sum queries.
44class NumArray {
45private:
46    unique_ptr<BinaryIndexedTree> tree; // Pointer to the Fenwick Tree
47
48public:
49    // Constructor with a given vector of numbers, initializes the Binary Indexed Tree.
50    NumArray(vector<int>& nums) {
51        int n = nums.size();
52        tree = make_unique<BinaryIndexedTree>(n);
53        // Initialize the tree with the initial values of 'nums'
54        for (int i = 0; i < n; ++i) tree->update(i + 1, nums[i]);
55    }
56
57    // Function to update an element of the array at a given 'index' with a new value 'val'.
58    void update(int index, int val) {
59        int current = sumRange(index, index);  // Get current value at the index
60        tree->update(index + 1, val - current); // Update the tree with the difference
61    }
62
63    // Function to calculate the sum of the elements in the range [left, right].
64    int sumRange(int left, int right) {
65        // Use tree queries to find the sum from 0 to 'right' and subtract the sum from 0 to 'left-1'
66        return tree->query(right + 1) - tree->query(left);
67    }
68};
69
70/**
71 * Your NumArray object will be instantiated and called as such:
72 * NumArray* obj = new NumArray(nums);
73 * obj->update(index, val);
74 * int param_2 = obj->sumRange(left, right);
75 */
76
1// Removed `#include <vector>` since it is C++ specific and not required in TypeScript
2
3// A type for representing a Binary Indexed Tree (or Fenwick Tree).
4type BinaryIndexedTree = {
5    size: number;       // The size of the array
6    treeArray: number[];  // The array that represents the tree
7};
8
9// Initialize the Binary Indexed Tree with a given size.
10function createBinaryIndexedTree(size: number): BinaryIndexedTree {
11    return {
12        size: size,
13        treeArray: new Array(size + 1).fill(0),  // Initialize with zeros and use size + 1 for 1-based indexing
14    };
15}
16
17// Update the value at a specific index in the Binary Indexed Tree.
18function update(tree: BinaryIndexedTree, index: number, delta: number): void {
19    while (index <= tree.size) {
20        tree.treeArray[index] += delta;  // Add 'delta' to current index
21        index += lowbit(index);          // Move to the next index that needs to be updated
22    }
23}
24
25// Calculate the prefix sum from the Binary Indexed Tree up to a given index.
26function query(tree: BinaryIndexedTree, index: number): number {
27    let sum = 0;
28    while (index > 0) {
29        sum += tree.treeArray[index];  // Add current value to the sum
30        index -= lowbit(index);        // Move to the next component of the prefix sum
31    }
32    return sum;
33}
34
35// Internal helper function to calculate the least significant bit that is set.
36function lowbit(x: number): number {
37    return x & (-x);
38}
39
40// Variables and methods to manage an array of numbers
41let tree: BinaryIndexedTree;
42
43// Initialize the Binary Indexed Tree with a given array of numbers.
44function createNumArray(nums: number[]): void {
45    let n = nums.length;
46    tree = createBinaryIndexedTree(n);
47    // Initialize the tree with the initial values of 'nums'
48    for (let i = 0; i < n; ++i) update(tree, i + 1, nums[i]);
49}
50
51// Update an element of the array at a given 'index' with a new value 'val'.
52function updateAtIndex(index: number, val: number): void {
53    let current = sumRange(index, index);  // Get current value at the index
54    update(tree, index + 1, val - current); // Update the tree with the difference
55}
56
57// Calculate the sum of the elements in the range [left, right].
58function sumRange(left: number, right: number): number {
59    // Use tree queries to find the sum from 0 to 'right' and subtract the sum from 0 to 'left - 1'
60    return query(tree, right + 1) - query(tree, left);
61}
62
63// The following lines of creating an instance of NumArray and calling its methods would be modified as follows:
64// Instead of:
65// NumArray* obj = new NumArray(nums);
66// obj->update(index, val);
67// int param_2 = obj->sumRange(left, right);
68//
69// The TypeScript version would be:
70// createNumArray(nums);
71// updateAtIndex(index, val);
72// let sum = sumRange(left, right);
73

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄