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]).

LeetCode

https://leetcode.com/problems/range-sum-query-immutable/description/

Constraints

1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
0 <= left <= right < nums.length
At most 10^4 calls will be made to sumRange.

Examples

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

Different Approaches

1️⃣ Brute Force Approach

🔧 Intuition:

For each query, iterate from left to right and sum the values.

🧠 Approach:

• Store the original array.
• Every time sumRange(l, r) is called, use a loop to calculate the sum.

🧾 C++ Code:

class NumArray {
public:
    vector<int> nums;

    NumArray(vector<int>& nums) {
        this->nums = nums;
    }

    int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++)
            sum += nums[i];
        return sum;
    }
};

Complexity Analysis:

• ⏱️Time Complexity:
  • Constructor: O(1)
  • sumRange: O(n) per query (worst-case: right - left + 1)
• 📦 Space Complexity: O(1)

2️⃣ Prefix Sum (Efficient and Optimal)

🔧 Intuition:

Instead of recomputing every time, precompute the cumulative sum so we can get the sum in O(1).

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

Then:

sumRange(left, right) = prefix[right + 1] - prefix[left]

🧠 Approach:

1. Create a prefix sum array prefix of size n + 1.
2. prefix[0] = 0, and for i > 0, prefix[i] = prefix[i-1] + nums[i-1]
3. For any query (l, r), return prefix[r+1] - prefix[l]

🧾 C++ Code:

class NumArray {
private:
    // This vector will store the prefix sums.
    // prefix[i] will hold the sum of the first i elements from the original array.
    vector<int> prefix;

public:
    // Constructor that is called when we create an object of NumArray
    NumArray(vector<int>& nums) {
        // Resize the prefix vector to be 1 longer than the input array
        // We use one extra space to make the logic easier (1-based index style)
        prefix.resize(nums.size() + 1, 0);

        // Fill the prefix sum array
        // prefix[0] is 0 by default
        // prefix[1] = nums[0], prefix[2] = nums[0] + nums[1], and so on
        for (int i = 0; i < nums.size(); ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    // Function to return the sum of elements from index 'left' to 'right' (inclusive)
    int sumRange(int left, int right) {
        // To get the sum from left to right:
        // We subtract the sum up to index 'left - 1' from the sum up to 'right'
        // Since prefix is 1-indexed, we do right + 1 and left
        return prefix[right + 1] - prefix[left];
    }
};

OR:

class NumArray {
public:
    // A vector to store the prefix sum of the input numbers
    vector<int> prefixSum;

    // Constructor - runs when the object is created
    NumArray(vector<int>& nums) {
        // Resize the prefixSum vector to have the same size as nums
        prefixSum.resize(nums.size(), 0);

        // Variable to keep track of the running sum
        int currentSum = 0;

        // Loop through each number in the input vector
        for (int i = 0; i < nums.size(); i++) {
            // Add the current number to the running sum
            currentSum += nums[i];

            // Store the running sum in the prefixSum array
            // prefixSum[i] now holds the sum of all elements from index 0 to i
            prefixSum[i] = currentSum;
        }
    }

    // Function to return the sum of elements between two indices, inclusive
    int sumRange(int left, int right) {
        // If the range starts at 0, just return prefixSum[right]
        // because prefixSum[right] already includes the sum from 0 to right
        if (left == 0) {
            return prefixSum[right];
        }

        // Otherwise, subtract the prefix sum up to left-1 from the sum up to right
        // This gives the sum from index left to right
        return prefixSum[right] - prefixSum[left - 1];
    }
};

/**
 * How to use:
 * NumArray* obj = new NumArray(nums);       // Create the object with your numbers
 * int param_1 = obj->sumRange(left, right); // Get the sum from index left to right
 */

Complexity Analysis:

• ⏱️ Time Complexity:
  • Constructor: O(n) to build prefix sum
  • sumRange: O(1) per query
• 📦 Space Complexity:
  • O(n) for prefix sum array