Range Sum

The range sum problem involves finding the sum of numbers in a given range. For example, given an array, we may want to find the sum of elements between indices i and j.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public static int rangeSum(int[] nums, int i, int j) {
  int sum = 0;
  for (int k = i; k <= j; k++) {
    sum += nums[k];
  }
  return sum;
}

int[] nums = {1, 2, 3, 4, 5};
int sum = rangeSum(nums, 1, 3); // returns 2 + 3 + 4 = 9

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int rangeSum(vector<int>& nums, int i, int j) {
  int sum = 0;
  for (int k = i; k <= j; k++) {
    sum += nums[k];
  }
  return sum;
}

vector<int> nums {1, 2, 3, 4, 5}; 
int sum = rangeSum(nums, 1, 3); // returns 9

Python example:

1
2
3
4
5
6
7
8

def range_sum(nums, i, j):
  sum = 0
  for k in range(i, j+1):
    sum += nums[k]
  return sum

nums = [1, 2, 3, 4, 5]
sum = range_sum(nums, 1, 3) # returns 9

The key steps are:

1. Initialize a sum variable

2. Loop through the given range, adding each element to the sum

3. Return the final sum

This allows efficiently finding the sum of a slice or range of a numeric array.

Range Sum is a computational problem where you’re given a list (or array) of numbers, and you need to find the sum of the numbers within a specific range (subarray) defined by its starting and ending indices. This problem can be encountered in various contexts and can be solved using different techniques.

Simple Approach

A simple approach to finding the range sum is to iterate over the elements within the given range and sum them up. This approach takes O(n) time complexity for each query, where n is the length of the range.

Python Example

1
2
3
4
5

def range_sum(arr, start, end):
    return sum(arr[start:end+1])

arr = [2, 4, 6, 8, 10]
print(range_sum(arr, 1, 3))  # Output: 18 (4 + 6 + 8)

Using Precomputation (Prefix Sum Array)

A more efficient way to find range sums is to use precomputation, specifically by creating a prefix sum array. The prefix sum array stores the sum of the elements from the beginning of the original array up to each index. With this precomputed array, you can find the sum of any range in constant time O(1).

Python Example with Prefix Sum Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def prefix_sum_array(arr):
    prefix_sum = [0]
    for num in arr:
        prefix_sum.append(prefix_sum[-1] + num)
    return prefix_sum

def range_sum(prefix_sum, start, end):
    return prefix_sum[end + 1] - prefix_sum[start]

arr = [2, 4, 6, 8, 10]
prefix_sum = prefix_sum_array(arr)
print(range_sum(prefix_sum, 1, 3))  # Output: 18 (4 + 6 + 8)

Key Takeaways

• Range Sum is a problem of finding the sum of elements within a specific range in an array.
• The naive approach iterates over the range, taking O(n) time for each query.
• Using a precomputed prefix sum array, the range sum can be found in constant time O(1), making it a highly efficient solution for handling multiple range sum queries.