Prefix Sum Array

Introduction

Prefix sum is a powerful technique used in competitive programming to optimize the time and space complexity of algorithms. By performing the necessary computations once and storing the results, subsequent queries can be answered efficiently using this precomputed data. This approach minimizes redundant calculations and significantly enhances performance.

To Calculate the Prefix Sum

1. Grab the previous value of the prefix sum.
2. Add the current value of the traversed array.

1D Prefix Sum

A 1D prefix sum is calculated from a 1D array by determining the cumulative sum of the array.

Example:

Array: [4, 6, 2, 1, 8]
Prefix Sum: [4, 10, 12, 13, 21]

The prefix sum array represents the cumulative sum of the elements up to each index of the original array.

Problem 1: Sub-array Sum for Multiple Queries

Given an array of integers and multiple index ranges, return the sum of the sub-array for each specified range.

Input:

arr: Array of integers
range: List of tuples, where each tuple contains the start and end indices of the sub-array
k: Number of ranges

Solution:

To solve this problem efficiently, we can use the prefix sum technique. First, we will calculate the prefix sum array, and then use it to quickly find the sum of any sub-array.


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

arr = [2, 4, 6, 8, 10] 
ranges = [(1, 3), (0, 2), (2, 4)]
k = 3 

for i in range(k):
    s,e = ranges[i]
    prefix = prefix_sum(arr)
    print(prefix[e+1]-prefix[s])

Two-Dimensional Prefix Sum

The two-dimensional (2D) prefix sum is an extension of the prefix sum technique applied to 2D arrays (matrices). It is used to quickly calculate the sum of elements in a sub-matrix. This method is particularly useful for solving problems that involve multiple queries for sub-matrix sums efficiently.

Calculation

To compute the 2D prefix sum, follow these steps:

Create a 2D prefix sum array prefix_sum with the same dimensions as the input matrix.
For each element in the matrix, calculate the prefix sum at that position by summing

The element itself
The prefix sum of the element directly above
The prefix sum of the element directly to the left
Subtract the prefix sum of the element diagonally above-left (to avoid double-counting)

Formula:

prefix[i−1][j] = prefix[i−1][j]+prefix[i][j−1] −prefix[i−1][j−1]+arr[i][j]

prefix[i][j] = prefix_top + prefix_left + arr[i][j] - prefix_top_left

Sum(ABCD)=Sum(OD)−Sum(OB)−Sum(OC)+Sum(OA)

Implementation: of problem 1using 2D array and 2D prefix sum


def compute_prefix_sum(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]

    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            prefix_sum[i][j] = (matrix[i-1][j-1] +
                                prefix_sum[i-1][j] +
                                prefix_sum[i][j-1] -
                                prefix_sum[i-1][j-1])
    return prefix_sum

def sum_submatrix(prefix_sum, r1, c1, r2, c2):
    return (prefix_sum[r2+1][c2+1] -
            prefix_sum[r1][c2+1] -
            prefix_sum[r2+1][c1] +
            prefix_sum[r1][c1])

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
prefix_sum = compute_prefix_sum(matrix)
result = sum_submatrix(prefix_sum, 1, 1, 2, 2)
print(result)  
# Output: 28 (sum of sub-matrix from (1,1) to (2,2))

Practice Problems

leetcode:

303. Range Sum Query - Immutable

724. Find Pivot Index

1004. Max Consecutive Ones III

Ticker

Prefix Sum Array

Introduction