Problem Description

Question

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

Constraints:

1 <= nums.length <= 3 * 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
At most 3 * 10⁴ calls will be made to update and sumRange.

Solve it on LeetCode

Approaches

1. Brute Force

Intuition:

Each update or sumRange query operates in constant time when using a brute force method.
On update operation, we simply change the value at the designated index.
On sumRange(i, j) operation, we iterate through the array from index i to j and calculate the sum.

This approach sacrifices performance for simplicity, offering an easy-to-understand solution at the cost of increased time complexity for range queries.

Code:

Complexity Analysis

Time Complexity:

update: O(1)
sumRange: O(n), where n is the number of elements between left and right.

Space Complexity: O(1) beyond the input storage, as we do not use any additional data structures besides a simple array.

2. Segment Tree

Intuition:

A Segment Tree is designed specifically to solve range query problems efficiently.
It pre-computes the range sums and supports efficient update and range sum operations.
With Segment Trees, both update and sumRange operations can be conducted in O(log n) time, balancing between brute force direct access and high efficiency.

Code:

Complexity Analysis

Time Complexity:

update: O(log n)
sumRange: O(log n)

Space Complexity: O(n), used by the segment tree structure.

3. Binary Indexed Tree (Fenwick Tree)

Intuition:

A Binary Indexed Tree (or Fenwick Tree) is another advanced data structure that supports prefix sum operations efficiently, similar to Segment Trees.
Fenwick Trees provide a simpler, more compact structure that allows both updates and prefix sum retrievals in O(log n) time.

Code:

Complexity Analysis

Time Complexity:

update: O(log n)
sumRange: O(log n)

Space Complexity: O(n), used by the Binary Indexed Tree structure.

Range Sum Query - Mutable

Ashish Pratap Singh

Problem Description

Example 1:

Constraints:

Solve it on LeetCode

Approaches

1. Brute Force

Intuition:

Code:

2. Segment Tree

Intuition:

Code:

3. Binary Indexed Tree (Fenwick Tree)

Intuition:

Code:

Get Premium