Leetcode 307. Range Sum Query - Mutable

Problem Explanation:

The problem is about a given integer array that supports two operations: update and sumRange.

• Update(i, val) modifies the array by updating the element at index i to val.
• SumRange(i, j) calculates the sum of all elements in the array from index i to j, inclusive.

The goal is to implement the NumArray class to carry out these two operations.

For example, given an array of [1, 3, 5], when we call sumRange(0, 2) it should return 9, which is sum of all the elements from index 0 to 2. Later, if we update the element at index 1 to 2 by calling update(1, 2), the array becomes [1, 2, 5]. Now, if we call sumRange(0, 2) again, it should return 8.

For this problem, we can use a data structure called Fenwick Tree or Binary Indexed Tree. This tree has the property that each node maintains the sum of a range of elements from the array, which can be efficiently updated and queried.

Solution Approach:

The Fenwick Tree is an efficient data structure for these kinds of operations. Indeed, each node of the tree maintains the prefix sum from the start of the array to a specific index, and these sums can be efficiently updated and queried. Here's how it works:

• The update(i, val) function updates node i with val and propagate this change to all the relevant nodes in the tree, which are determined by adding the "lowbit" of i, a bitwise operation that returns the value of the least significant non-zero bit of i.

• The sumRange(i, j) function simply returns the difference between the prefix sums up to j + 1 and i.

For example, let's see how the tree is constructed for an array [1, 3, 5]:

Array: [1, 3, 5] -> Fenwick Tree (0-based index): [1, 4, 5, 9], where 4 is sum of 1 and 3, and 9 is sum of 1, 3, and 5

After update(1, 2), the array becomes [1, 2, 5], and the Fenwick Tree becomes: [1, 3, 5, 8], where 3 is sum of 1 and 2, and 8 is sum of 1, 2, and 5

Solution in Python:

1
2python
3class FenwickTree:
4    def __init__(self, n):
5        self.sums = [0]*(n + 1)
6
7    def update(self, i, delta):
8        while i < len(self.sums):
9            self.sums[i] += delta
10            i += i & -i   # moving to next index for updating
11
12    def get(self, i):
13        res = 0
14        while i > 0:
15            res += self.sums[i]
16            i -= i & -i  # moving to previous index for getting the sum
17        return res
18
19class NumArray:
20    def __init__(self, nums):
21        self.nums = nums
22        self.tree = FenwickTree(len(nums))
23        for i, num in enumerate(nums):
24            self.tree.update(i + 1, num)
25
26    def update(self, index, val):
27        self.tree.update(index + 1, val - self.nums[index]) # updating the fenwick tree
28        self.nums[index] = val
29
30    def sumRange(self, left, right):
31        return self.tree.get(right + 1) - self.tree.get(left)  # get sum from fenwick tree

Solution in Java:

1
2java
3class FenwickTree {
4    private int[] sums;
5
6    public FenwickTree(int n) {
7        sums = new int[n + 1];
8    }
9
10    public void update(int i, int delta) {
11        while (i < sums.length) {
12            sums[i] += delta;
13            i += lowbit(i);
14        }
15    }
16
17    public int get(int i) {
18        int sum = 0;
19        while (i > 0) {
20            sum += sums[i];
21            i -= lowbit(i);
22        }
23        return sum;
24    }
25
26    private int lowbit(int i) {
27        return i & (-i);
28    }
29}
30
31class NumArray {
32    private FenwickTree tree;
33    private int[] nums;
34
35    public NumArray(int[] nums) {
36        this.tree = new FenwickTree(nums.length);
37        this.nums = nums;
38        for (int i = 0; i < nums.length; ++i)
39            tree.update(i + 1, nums[i]);
40    }
41
42    public void update(int i, int val) {
43        tree.update(i + 1, val - nums[i]);
44        nums[i] = val;
45    }
46
47    public int sumRange(int i, int j) {
48        return tree.get(j + 1) - tree.get(i);
49    }
50}

Solution in JavaScript:

1
2javascript
3class NumArray {
4    constructor(nums) {
5        this.len = nums.length;
6        this.tree = Array(this.len + 1).fill(0);
7        this.nums = Array(this.len).fill(0);
8        for (let i = 0; i < this.len; i++) {
9            this.update(i, nums[i]);
10        }
11    }
12
13    _lowbit(i) {
14        return i & (-i);
15    }
16
17    update(i, j) {
18        let oldVal = this.nums[i],
19            node = i + 1;
20        this.nums[i] = j;
21        while (node <= this.len) {
22            this.tree[node] += j - oldVal;
23            node += this._lowbit(node);
24        } 
25    }
26
27    sumRange(i, j) {
28        let sum1 = 0, sum2 = 0, node1 = i, node2 = j + 1;
29        while (node2 > 0) {
30            sum2 += this.tree[node2];
31            node2 -= this._lowbit(node2);
32        }
33        while (node1 > 0) {
34            sum1 += this.tree[node1];
35            node1 -= this._lowbit(node1);
36        }
37        return sum2 - sum1;
38    }
39}

Solution in C++:

1
2c++
3class FenwickTree {
4    public:
5    vector<int> sums;
6
7    FenwickTree(int n) : sums(n + 1, 0) {}
8
9    void update(int index, int delta) {
10        while (index<sums.size()) {
11            sums[index] += delta;
12            index += index & -index;
13        }
14    }
15
16    int get(int index) {
17        int sum = 0;
18        while (index > 0) {
19            sum += sums[index];
20            index -= index & -index;
21        }
22        return sum;
23    }
24};
25
26class NumArray {
27    public:
28    vector<int> nums;
29    FenwickTree tree;
30
31    NumArray(vector<int>& nums) : nums(nums), tree(nums.size()) {
32        for (int i = 0; i < nums.size(); ++i)
33            tree.update(i + 1, nums[i]);
34    }
35
36    void update(int index, int val) {
37        tree.update(index + 1, val - nums[index]);
38        nums[index] = val;
39    }
40
41    int sumRange(int left, int right) {
42        return tree.get(right + 1) - tree.get(left);
43    }
44};

Solution in C#:

1
2C#
3public class NumArray {
4    int[] B, nums;            
5    
6    public NumArray(int[] nums) {
7        this.nums = nums;
8        int len = nums.Length;
9        B = new int[len + 1];
10        for (int i = 0; i < len; i++)
11            Increase(i, nums[i]);
12    }
13
14    public void Increase(int i, int val) {
15        int index = i + 1;
16        while (index < B.Length) {
17            B[index] += val;
18            index = index + (index & -index);
19        }
20    }
21
22    public int Sum(int i) {
23        int sum = 0;
24        int index = i + 1;
25        while (index > 0) {
26            sum += B[index];
27            index = index - (index & -index);
28        }
29        return sum;
30    }
31
32    public void Update(int i, int val) {
33        Increase(i, val - nums[i]);
34        nums[i] = val;
35    }
36
37    public int SumRange(int i, int j) {
38        return Sum(j) - Sum(i - 1);
39    }
40}

In all the above solutions, we first construct a binary indexed tree (Fenwick tree) with 'n + 1' nodes, where 'n' is the length of the input array. We fill this tree using the numbers in the input array.

For the update method, we first calculate the difference 'delta' between the new value and the current value at the specified index. This 'delta' is then added to the appropriate nodes in the Fenwick tree.

For the sumRange method, we calculate and return the difference between the prefix sums up to 'right + 1' and 'left'.

By using a Fenwick tree, both the update and sumRange operations can be done in O(logn) time complexity. This is significantly faster than using a simple array or list data structure, where the time complexity would be O(n) for these operations.

The space complexity for these solutions is also O(n), as we need to store 'n + 1' elements in the Fenwick tree, and 'n' elements in the original array. But again, compared to other potential solutions like segment trees, these solutions are more space-efficient.

So, these solutions provide a good balance of time efficiency and space efficiency for the given problem. They also provide an example of how the Fenwick tree can be used for efficient range queries and updates in an array.