Problem

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. The update(i, val) function modifies nums by updating the element at index i to val.

OR

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

  1. Update the value of an element in nums.
  2. 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]).

Solution

Method 1 - Naive

A basic approach involves iterating through the range from l to r to compute the sum of elements. Updating a value can be done directly with nums[i] = x. This results in the sum operation taking O(n) time and the update operation taking O(1) time.

Alternatively, another array can be constructed to store the cumulative sum up to the ith index. This allows range sums to be calculated in O(1) time but makes update operations take O(n) time. This approach is suitable when query operations are frequent but updates are rare.

Method 2 - Segment Tree

To solve the problem efficiently, we can use a Segment Tree data structure to handle two types of operations:

  1. Update queries to change values at specific indices in the array.
  2. Range sum queries to compute the sum of elements within a given range.

The Segment Tree allows us to perform both update and range sum operations efficiently in O(log n) time.

Representation of Segment Tree

  1. The leaf nodes in a segment tree correspond to the elements of the input array.
  2. Each internal node represents the result of merging its child nodes, with the type of merging depending on the problem. For this problem, the merging is the sum of the elements under a node. Segment trees are often represented using arrays: the left child of a node at index i is at 2*i+1, the right child at 2*i+2, and the parent node at (i-1)/2.

Construction of Segment Tree

To construct a segment tree, start with the segment arr[0...n-1]. Recursively divide the segment into two halves (unless it is already of length 1) and repeat the process for each half. At every segment, store the sum in the corresponding tree node.

The segment tree is a Full Binary Tree because segments are always split into two halves. All tree levels, except possibly the last one, are completely filled. With n leaves, there are n-1 internal nodes, making the total number of nodes 2*n - 1. The height of the tree is log2(n). Representing the tree as an array requires memory proportional to 2 * 2^log2(n) - 1 to maintain parent-child relationships.

Querying for sum of given range

After constructing the segment tree, we can retrieve the sum of elements using it. Below is the algorithm to compute the sum in the segment tree.

Updation of value

Similar to tree construction and query operations, updates can be performed recursively. For a given index to update, let diff represent the value to be added. Starting from the root of the segment tree, diff is added to all nodes whose range includes the specified index. Nodes that do not include the index in their range remain unchanged.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class NumArray {

    private int[] segTree;
    private int n;

    public NumArray(int[] nums) {
        n = nums.length;
        segTree = new int[4 * n];
        buildTree(nums, 0, n - 1, 0);
    }

    private void buildTree(int[] nums, int left, int right, int pos) {
        if (left == right) {
            segTree[pos] = nums[left];
            return;
        }
        int mid = left + (right - left) / 2;
        buildTree(nums, left, mid, 2 * pos + 1);
        buildTree(nums, mid + 1, right, 2 * pos + 2);
        segTree[pos] = segTree[2 * pos + 1] + segTree[2 * pos + 2];
    }

    public void update(int index, int val) {
        updateTree(index, val, 0, n - 1, 0);
    }

    private void updateTree(int index, int val, int left, int right, int pos) {
        if (left == right) {
            segTree[pos] = val;
            return;
        }
        int mid = left + (right - left) / 2;
        if (index <= mid) {
            updateTree(index, val, left, mid, 2 * pos + 1);
        } else {
            updateTree(index, val, mid + 1, right, 2 * pos + 2);
        }
        segTree[pos] = segTree[2 * pos + 1] + segTree[2 * pos + 2];
    }

    public int sumRange(int left, int right) {
        return queryTree(left, right, 0, n - 1, 0);
    }

    private int queryTree(int qLeft, int qRight, int left, int right, int pos) {
        if (qLeft <= left && qRight >= right) {
            return segTree[pos];
        }
        if (qLeft > right || qRight < left) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        return (
            queryTree(qLeft, qRight, left, mid, 2 * pos + 1) +
            queryTree(qLeft, qRight, mid + 1, right, 2 * pos + 2)
        );
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    class NumArray:
        def __init__(self, nums: list[int]) -> None:
            self.n = len(nums)
            self.seg_tree = [0] * (4 * self.n)
            self._build_tree(nums, 0, self.n - 1, 0)

        def _build_tree(self, nums: list[int], left: int, right: int, pos: int) -> None:
            if left == right:
                self.seg_tree[pos] = nums[left]
                return
            mid = left + (right - left) // 2
            self._build_tree(nums, left, mid, 2 * pos + 1)
            self._build_tree(nums, mid + 1, right, 2 * pos + 2)
            self.seg_tree[pos] = self.seg_tree[2 * pos + 1] + self.seg_tree[2 * pos + 2]

        def update(self, index: int, val: int) -> None:
            self._update_tree(index, val, 0, self.n - 1, 0)

        def _update_tree(self, index: int, val: int, left: int, right: int, pos: int) -> None:
            if left == right:
                self.seg_tree[pos] = val
                return
            mid = left + (right - left) // 2
            if index <= mid:
                self._update_tree(index, val, left, mid, 2 * pos + 1)
            else:
                self._update_tree(index, val, mid + 1, right, 2 * pos + 2)
            self.seg_tree[pos] = self.seg_tree[2 * pos + 1] + self.seg_tree[2 * pos + 2]

        def sumRange(self, left: int, right: int) -> int:
            return self._query_tree(left, right, 0, self.n - 1, 0)

        def _query_tree(self, q_left: int, q_right: int, left: int, right: int, pos: int) -> int:
            if q_left <= left and q_right >= right:
                return self.seg_tree[pos]
            if q_left > right or q_right < left:
                return 0
            mid = left + (right - left) // 2
            return self._query_tree(q_left, q_right, left, mid, 2 * pos + 1) + \
                self._query_tree(q_left, q_right, mid + 1, right, 2 * pos + 2)

Complexity

  • ⏰ Time complexity
    • Building the segment tree: O(n) (because we initialise all nodes in the tree).
    • Range sum query: O(log n) (since we traverse the tree height for queries).
    • Update operation: O(log n) (similar reasoning as querying).
  • 🧺 Space complexity: O(4*n) space as the array is stored in a binary tree structure with some extra storage for intermediate nodes.

Method 3 - Binary Index Tree / Fenwick Tree

We can use a Fenwick Tree (or Binary Indexed Tree) to handle the same operations efficiently. Fenwick Tree allows:

  1. Range sum queries and
  2. Update operations in O(log n) time.

Fenwick Tree is an efficient data structure based on prefix sums. Each node (or index) keeps track of the cumulative sum of a certain range, allowing us to calculate range sums and update indices efficiently by adjusting sums in the tree.

Operations

  1. Update:
    • When a value at index index is updated, we propagate the difference (delta = newValue - oldValue) to update the cumulative sums stored in the tree.
    • For each update, the relevant indices are updated incrementally based on powers of two in the binary representation.
  2. Query:
    • To compute the sum of elements between indices left and right, we use prefix sums:
      • sumRange(left, right) = prefixSum(right) - prefixSum(left - 1)
    • The prefix sum is easily calculated using the Fenwick Tree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class NumArray {

    private int[] nums;
    private int[] fenwickTree;
    private int n;

    public NumArray(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        this.fenwickTree = new int[n + 1]; // Fenwick Tree is 1-indexed
        for (int i = 0; i < n; i++) {
            _updateFenwick(i + 1, nums[i]);
        }
    }

    private void _updateFenwick(int index, int delta) {
        while (index <= n) {
            fenwickTree[index] += delta;
            index += index & -index; // Move to the next parent in the tree
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val; // Update the original array
        _updateFenwick(index + 1, delta); // Update the Fenwick Tree
    }

    public int sumRange(int left, int right) {
        return _queryFenwick(right + 1) - _queryFenwick(left);
    }

    private int _queryFenwick(int index) {
        int sum = 0;
        while (index > 0) {
            sum += fenwickTree[index];
            index -= index & -index; // Move to parent in the tree
        }
        return sum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class NumArray:
    def __init__(self, nums: list[int]) -> None:
        self.n = len(nums)
        self.nums = nums
        self.fenwick_tree = [0] * (self.n + 1)  # Fenwick Tree is 1-indexed
        for i in range(self.n):
            self._update_fenwick(i + 1, nums[i])

    def _update_fenwick(self, index: int, delta: int) -> None:
        while index <= self.n:
            self.fenwick_tree[index] += delta
            index += index & -index  # Move to the next parent in the tree

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val  # Update the original array
        self._update_fenwick(index + 1, delta)  # Update the Fenwick Tree

    def sumRange(self, left: int, right: int) -> int:
        return self._query_fenwick(right + 1) - self._query_fenwick(left)

    def _query_fenwick(self, index: int) -> int:
        sum_ = 0
        while index > 0:
            sum_ += self.fenwick_tree[index]
            index -= index & -index  # Move to the parent in the tree
        return sum_

Complexity

  • ⏰ Time complexity
    • Update operation: O(log n) (due to traversal of the tree to update cumulative sums at relevant indices).
    • Range sum query: O(log n) (prefix sums are computed by traversing the tree).
  • 🧺 Space complexity: O(n) (tree size proportional to the array size).