Range Sum Query

📘 Problem Statement

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

1. 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.
• 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

Example 1

Input

["NumArray", "sumRange", "sumRange", "sumRange"]

[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output [null, 1, -1, -3]

Explanation

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

---

🛠️ Solution

❌ Brute Force Approach (Inefficient)

For each sumRange(i, j), loop from i to j and sum the elements.

Time Complexity:

Each query: \(O(n)\) in the worst case If there are q queries: \(O(q·n)\) total

⚡ Optimized Approach: Prefix Sum

🔑 Key Idea:

Precompute a prefix sum array where:

prefix_sum[k] = sum of nums[0] to nums[k - 1]

Then:

sumRange(i, j) = prefix_sum[j + 1] - prefix_sum[i]

class NumArray:
    def __init__(self, nums):
        self.prefix_sum = [0]  # prefix_sum[0] = 0
        for num in nums:
            self.prefix_sum.append(self.prefix_sum[-1] + num)

    def sumRange(self, left, right):
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

⏱️ Time & Space Complexity

Operation	Time	Space
Constructor	\(O(n)\)	\(O(n)\) (prefix array)
sumRange()	\(O(1)\)	—