Solution: Range Sum Query - Immutable

Explore how to efficiently handle multiple range sum queries on an immutable array by implementing a prefix sum array. Understand the construction and use of the NumArray class, which allows constant time sum retrieval between any two indices. This lesson teaches the importance of prefix sums in optimizing query operations and balancing time and space complexity.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given an integer array, nums, and you need to handle multiple queries of the following type:

Query: Calculate the sum of elements in nums between indices i and j (inclusive), where i <= j.

Implement the NumArray class to support the following operations efficiently:

Constructor: Initializes the object with the integer array nums.
sumRange(i, j): Returns the sum of the elements of nums between indices i and j (inclusive), i.e., the sum of nums[i] + nums[i + 1] + ... + nums[j].

Constraints:

$1 \leq$ nums.length $\leq 10^3$
$-10^5 \leq$ nums[i] ...