For each sumRange query, iterate through the array from index left to right and compute the sum directly. This is straightforward but inefficient for repeated queries.
Precompute a prefix sum array where prefix[i] stores the sum of elements from index 0 to i - 1. To get the sum of any range [left, right], simply compute prefix[right + 1] - prefix[left]. This gives constant-time queries after linear-time preprocessing.
""" 0303.1 - Range Sum Query - Immutable - Solution 1 - Brute Force """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class NumArray:
"""NumArray Class"""
def __init__(self, nums: List[int]):
"""Initialize with the given array"""
self.nums = nums
def sumRange(self, left: int, right: int) -> int:
"""Sum Range Function"""
total = 0
for i in range(left, right + 1):
total += self.nums[i]
return total
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
obj = NumArray([-2, 0, 3, -5, 2, -1])
print(obj.sumRange(0, 2)) # 1
print(obj.sumRange(2, 5)) # -1
print(obj.sumRange(0, 5)) # -3
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0303.2 - Range Sum Query - Immutable - Solution 2 - Prefix Sum """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class NumArray:
"""NumArray Class"""
def __init__(self, nums: List[int]):
"""Initialize with prefix sum array"""
self.prefix = [0]
cur = 0
for n in nums:
cur += n
self.prefix.append(cur)
def sumRange(self, left: int, right: int) -> int:
"""Sum Range Function"""
return self.prefix[right + 1] - self.prefix[left]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
obj = NumArray([-2, 0, 3, -5, 2, -1])
print(obj.sumRange(0, 2)) # 1
print(obj.sumRange(2, 5)) # -1
print(obj.sumRange(0, 5)) # -3
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()