Prefix Sums in One-Dimensional Arrays

LeetCode Problem: Range Sum Query - Immutable

Problem Overview

Given an integer array nums, implement a data structure that can efficiently answer multiple queries for the sum of elements between indices left and right inculsive.

Core Idea

Instead of recalculating the sum for every query, we precompute a prefix sum array. The element at index i in this auxiliary array stores the sum of all elements in the original array from index 0 to i-1. This allows any range sum query to be answered in constant time with a single subtraction.

Implementation

#include <stdio.h>
#include <stdlib.h>

// Data structure to hold the prefix sum array
typedef struct {
    int* prefixSums;  // Array storing cumulative sums
} RangeSumCalculator;

// Constructor: Builds the prefix sum array
RangeSumCalculator* createRangeSumCalculator(int* nums, int numsSize) {
    RangeSumCalculator* calc = (RangeSumCalculator*)malloc(sizeof(RangeSumCalculator));
    // Allocate space for prefix sums (size is numsSize + 1 for easier indexing)
    calc->prefixSums = (int*)malloc(sizeof(int) * (numsSize + 1));
    calc->prefixSums[0] = 0; // Base case: sum of zero elements is 0

    // Compute cumulative sums
    for (int i = 1; i <= numsSize; i++) {
        calc->prefixSums[i] = calc->prefixSums[i - 1] + nums[i - 1];
    }
    return calc;
}

// Query Method: Returns sum of nums[left..right] inclusive
int calculateRangeSum(RangeSumCalculator* calc, int left, int right) {
    // Sum from 0 to right minus sum from 0 to (left-1)
    return calc->prefixSums[right + 1] - calc->prefixSums[left];
}

// Destructor: Frees allocated memory
void destroyRangeSumCalculator(RangeSumCalculator* calc) {
    free(calc->prefixSums);
    free(calc);
}

int main() {
    // Example usage
    int data[] = {1, 2, 3, 4, 5};
    int size = sizeof(data) / sizeof(data[0]);

    RangeSumCalculator* calc = createRangeSumCalculator(data, size);

    // Query: Sum of elements from index 1 to 3 (2+3+4)
    int result = calculateRangeSum(calc, 1, 3);
    printf("Range Sum (1 to 3) = %d\n", result); // Output: 9

    destroyRangeSumCalculator(calc);
    return 0;
}

How It Works

Consider the prefix sum array preSum. To find the sum of the original array from index left to right: sum = preSum[right + 1] - preSum[left]

For example, with nums = [1, 2, 3, 4, 5]:

• preSum = [0, 1, 3, 6, 10, 15]
• To get sum(nums[1..4]) which is 2+3+4+5=14:
  • preSum[5] - preSum[1] = 15 - 1 = 14

This reduces the time complexity of each query from O(N) to O(1), after an O(N) preprocessing step.

Real-World Analogy

Imagine a class where each student has a final exam score (0-100). To quickly answer queries like "how many students scored between 75 and 90?", you could:

1. Create a frequency array count[101] where count[s] is the number of students with score s.
2. Build a prefix sum array from count.
3. Answer any score range query with: countPrefix[high] - countPrefix[low-1].

---

Prefix Sums in Two-Dimensional Matrices

LeetCode Problem: Range Sum Query 2D - Immutable

Problem Overview

Given a 2D matrix, implement a data structure to efficiently calculate the sum of elements inside a rectangular submatrix defined by its top-left and bottom-right corners.

Core Idea

Extend the prefix sum concept to two dimensions. We precompute a 2D prefix sum matrix where prefixSum[i][j] represents the sum of all element in the submatrix from (0,0) to (i-1, j-1). Any rectangular sum can then be computed using the inclusion-exclusion principle with just four lookups.

Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int** prefixSums; // 2D prefix sum matrix
} MatrixSumCalculator;

// Constructor: Builds the 2D prefix sum matrix
MatrixSumCalculator* createMatrixSumCalculator(int** matrix, int rows, int cols) {
    if (rows == 0 || cols == 0) return NULL;

    MatrixSumCalculator* calc = (MatrixSumCalculator*)malloc(sizeof(MatrixSumCalculator));
    // Allocate (rows+1) x (cols+1) matrix for easier indexing
    calc->prefixSums = (int**)malloc(sizeof(int*) * (rows + 1));
    for (int i = 0; i <= rows; i++) {
        calc->prefixSums[i] = (int*)calloc(cols + 1, sizeof(int));
    }

    // Compute 2D prefix sums
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            // Current cell sum = sum above + sum left - sum diagonal + original value
            calc->prefixSums[i][j] = calc->prefixSums[i-1][j] + calc->prefixSums[i][j-1]
                                   - calc->prefixSums[i-1][j-1] + matrix[i-1][j-1];
        }
    }
    return calc;
}

// Query Method: Sum of submatrix (row1, col1) to (row2, col2) inclusive
int calculateSubmatrixSum(MatrixSumCalculator* calc, int row1, int col1, int row2, int col2) {
    // Use inclusion-exclusion principle
    return calc->prefixSums[row2+1][col2+1] - calc->prefixSums[row1][col2+1]
           - calc->prefixSums[row2+1][col1] + calc->prefixSums[row1][col1];
}

// Destructor: Frees allocated memory
void destroyMatrixSumCalculator(MatrixSumCalculator* calc) {
    if (!calc) return;
    for (int i = 0; i <= sizeof(calc->prefixSums)/sizeof(int*); i++) {
        free(calc->prefixSums[i]);
    }
    free(calc->prefixSums);
    free(calc);
}

int main() {
    // Example: 3x3 matrix
    int* matrix[3];
    int data[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    for (int i = 0; i < 3; i++) matrix[i] = data[i];

    MatrixSumCalculator* calc = createMatrixSumCalculator(matrix, 3, 3);

    // Query: Sum of submatrix from (0,0) to (1,1) -> 1+2+4+5
    int result = calculateSubmatrixSum(calc, 0, 0, 1, 1);
    printf("Submatrix Sum = %d\n", result); // Output: 12

    destroyMatrixSumCalculator(calc);
    return 0;
}

Visual Explanation

To find the sum of a submatrix (red area), we can use the precomputed sums of larger rectangles starting from the origin (0,0):

Sum(Red) = Sum(Green) - Sum(Blue) - Sum(Orange) + Sum(Pink)

Where:

• Green: Rectangle from (0,0) to bottom-right corner of red.
• Blue: Rectangle above red.
• Orange: Rectangle left of red.
• Pink: Rectangle diagonally adjacent (subtracted twice, so added back once).

This formula is implemented in the calculateSubmatrixSum function.

---

Application: Counting Subarrays with a Given Sum

LeetCode Problem: Subarray Sum Equals K

Problem Overview

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k.

Initial Approach (O(N²) Time)

A straightforward method uses the prefix sum array and checks all possible subarrays.

#include <stdio.h>
#include <stdlib.h>

int countSubarraysWithSum(int* nums, int numsSize, int k) {
    // Build prefix sum array
    int* prefixSums = (int*)malloc(sizeof(int) * (numsSize + 1));
    prefixSums[0] = 0;
    for (int i = 0; i < numsSize; i++) {
        prefixSums[i + 1] = prefixSums[i] + nums[i];
    }

    int count = 0;
    // Check all subarrays nums[j..i-1]
    for (int i = 1; i <= numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (prefixSums[i] - prefixSums[j] == k) {
                count++;
            }
        }
    }
    free(prefixSums);
    return count;
}

int main() {
    int data[] = {1, 2, 3, 4, 5};
    int target = 3;
    int size = sizeof(data) / sizeof(data[0]);

    int result = countSubarraysWithSum(data, size, target);
    printf("Subarrays with sum %d: %d\n", target, result);
    return 0;
}

Optimization Insight

The inner loop searches for indices j where prefixSums[j] == prefixSums[i] - k. We can optimize by using a hash map to store the frequency of prefix sums encountered so far, eliminating the inner loop.

Optimized Solution (O(N) Time)

#include <stdio.h>
#include <stdlib.h>

// Simple hash map entry structure
typedef struct {
    int key;
    int value;
} HashEntry;

typedef struct {
    HashEntry* table;
    int capacity;
} FrequencyMap;

FrequencyMap* createMap(int capacity) {
    FrequencyMap* map = (FrequencyMap*)malloc(sizeof(FrequencyMap));
    map->table = (HashEntry*)calloc(capacity, sizeof(HashEntry));
    map->capacity = capacity;
    return map;
}

void updateMap(FrequencyMap* map, int key, int value) {
    int index = abs(key) % map->capacity;
    // Linear probing for collision resolution
    while (map->table[index].value != 0 && map->table[index].key != key) {
        index = (index + 1) % map->capacity;
    }
    map->table[index].key = key;
    map->table[index].value = value;
}

int getFrequency(FrequencyMap* map, int key, int defaultVal) {
    int index = abs(key) % map->capacity;
    while (map->table[index].value != 0 && map->table[index].key != key) {
        index = (index + 1) % map->capacity;
    }
    return (map->table[index].value != 0) ? map->table[index].value : defaultVal;
}

int countSubarraysWithSumOptimized(int* nums, int numsSize, int k) {
    FrequencyMap* prefixSumFreq = createMap(numsSize + 1);
    // Base case: a prefix sum of 0 has occurred once (before processing any element)
    updateMap(prefixSumFreq, 0, 1);

    int currentSum = 0, totalCount = 0;
    for (int i = 0; i < numsSize; i++) {
        currentSum += nums[i]; // prefix sum up to index i
        // We need prefixSum[i] - prefixSum[j] = k
        // => prefixSum[j] = prefixSum[i] - k
        // Check how many previous prefix sums match this value
        int requiredSum = currentSum - k;
        totalCount += getFrequency(prefixSumFreq, requiredSum, 0);
        // Update frequency of the current prefix sum
        int currentFreq = getFrequency(prefixSumFreq, currentSum, 0);
        updateMap(prefixSumFreq, currentSum, currentFreq + 1);
    }

    free(prefixSumFreq->table);
    free(prefixSumFreq);
    return totalCount;
}

int main() {
    int data[] = {1, 1, 1};
    int target = 2;
    int size = sizeof(data) / sizeof(data[0]);

    int result = countSubarraysWithSumOptimized(data, size, target);
    printf("Subarrays with sum %d: %d\n", target, result); // Output: 2
    return 0;
}

Key Insight

If the sum of elements from index j to i is k, then: prefixSum[i] - prefixSum[j-1] = k Rearranging: prefixSum[j-1] = prefixSum[i] - k

Therefore, as we iterate, for each prefixSum[i], we count how many previous prefix sums equal prefixSum[i] - k. This is efficiently tracked with a hash map.

---

Summary

Prefix sums are a fundamental technique for optimizing range sum queries:

1. 1D Arrays: Transform O(N) queries into O(1) after O(N) preprocessing.
2. 2D Matrices: Transform O(MN) queries into O(1) after O(MN) preprocessing using the inclusion-exclusion principle.
3. Subarray Problems: Enable O(N) solutions for problems like counting subarrays with a given sum by combining prefix sums with hash maps.

The power of this technique lies in shifting computation from query time to preprocessing time, making it ideal for scenarios with multiple queries on static or semi-static data.