Tag prefix sum technique

Prefix Sum Array – Implementation in C: A Comprehensive Tutorial

A prefix sum array is a precomputed array where each element at index i stores the sum of all elements from index 0 to i in the original array. This simple yet powerful technique enables O(1) range-sum queries after O(n) preprocessing, making it a cornerstone of many array and range-query algorithms.

This tutorial provides an in-depth exploration of prefix sum arrays in C: concepts, implementation, range-sum queries, 2D prefix sums, practical applications, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is a Prefix Sum Array?

Given an array arr[], the prefix sum array prefixSum[] is defined as:

text

prefixSum[i] = arr[0] + arr[1] + ... + arr[i]

Example:

text

Input: [10, 20, 10, 5, 15] Prefix Sum: [10, 30, 40, 45, 60]

Why Prefix Sums Matter

• Range sum queries: O(1) after O(n) preprocessing.
• Foundation for many problems: Subarray sums, equilibrium index, split arrays.
• 2D prefix sums: Rectangle sum queries in matrices.
• Sliding window alternatives: When the array is static.
• Competitive programming: Essential preprocessing technique.

Key Insight: Range Sum in O(1)

For a range [L, R] (inclusive):

text

sum(L, R) = prefixSum[R] - prefixSum[L - 1] (if L > 0) sum(0, R) = prefixSum[R] (if L == 0)

Complexity Comparison

Operation	Without Prefix Sum	With Prefix Sum
Preprocessing	O(1)	O(n)
Range sum query	O(n)	O(1)
Q queries	O(n × Q)	O(n + Q)

---

Syntax & Core Mechanics

Basic Prefix Sum Implementation

c

#include <stdio.h> #include <stdlib.h> int *buildPrefixSum(const int arr[], int n) { if (n <= 0) return NULL; int *prefix = malloc(n * sizeof(int)); if (prefix == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return NULL; } prefix[0] = arr[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; } return prefix; } int main(void) { int arr[] = {10, 20, 10, 5, 15}; int n = sizeof(arr) / sizeof(arr[0]); int *prefix = buildPrefixSum(arr, n); if (prefix == NULL) return 1; printf("Original: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); printf("Prefix sum: "); for (int i = 0; i < n; i++) printf("%d ", prefix[i]); printf("\n"); free(prefix); return 0; }

Expected output:

text

Original: 10 20 10 5 15 Prefix sum: 10 30 40 45 60

Time: O(n), Space: O(n)

Range Sum Query

c

/* Returns sum of arr[L..R] inclusive */ long long rangeSum(const long long prefix[], int L, int R) { if (L < 0 || R < 0 || L > R) return 0; if (L == 0) return prefix[R]; return prefix[R] - prefix[L - 1]; } int main(void) { int arr[] = {10, 20, 10, 5, 15}; int n = 5; long long prefix[5]; prefix[0] = arr[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; } printf("Sum[1..3] = %lld\n", rangeSum(prefix, 1, 3)); /* 20+10+5 = 35 */ printf("Sum[0..4] = %lld\n", rangeSum(prefix, 0, 4)); /* 60 */ printf("Sum[2..2] = %lld\n", rangeSum(prefix, 2, 2)); /* 10 */ printf("Sum[3..4] = %lld\n", rangeSum(prefix, 3, 4)); /* 5+15 = 20 */ return 0; }

Expected output:

text

Sum[1..3] = 35 Sum[0..4] = 60 Sum[2..2] = 10 Sum[3..4] = 20

1-Indexed Prefix Sum (Convenient for Range Queries)

Using a 1-indexed prefix array simplifies range queries (no special case for L == 0).

c

/* prefix[0] = 0, prefix[i] = sum(arr[0..i-1]) */ void buildPrefix1Indexed(const int arr[], int n, long long prefix[]) { prefix[0] = 0; for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + arr[i - 1]; } } /* Range sum [L, R] inclusive (0-based) */ long long rangeSum1(const long long prefix[], int L, int R) { return prefix[R + 1] - prefix[L]; } int main(void) { int arr[] = {10, 20, 10, 5, 15}; int n = 5; long long prefix[6]; buildPrefix1Indexed(arr, n, prefix); printf("prefix array: "); for (int i = 0; i <= n; i++) printf("%lld ", prefix[i]); printf("\n"); printf("Sum[1..3] = %lld\n", rangeSum1(prefix, 1, 3)); /* 35 */ printf("Sum[0..4] = %lld\n", rangeSum1(prefix, 0, 4)); /* 60 */ return 0; }

Expected output:

text

prefix array: 0 10 30 40 45 60 Sum[1..3] = 35 Sum[0..4] = 60

2D Prefix Sum (Matrix Rectangle Sum)

For a matrix, prefix[i][j] stores the sum of the submatrix from (0,0) to (i,j).

Formula:

text

prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

Rectangle sum from (r1, c1) to (r2, c2):

text

sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

c

#include <stdio.h> #include <stdlib.h> #define ROWS 3 #define COLS 4 void build2DPrefix(int matrix[ROWS][COLS], int prefix[ROWS][COLS]) { for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { prefix[i][j] = matrix[i][j]; if (i > 0) prefix[i][j] += prefix[i - 1][j]; if (j > 0) prefix[i][j] += prefix[i][j - 1]; if (i > 0 && j > 0) prefix[i][j] -= prefix[i - 1][j - 1]; } } } int rectSum(int prefix[ROWS][COLS], int r1, int c1, int r2, int c2) { int sum = prefix[r2][c2]; if (r1 > 0) sum -= prefix[r1 - 1][c2]; if (c1 > 0) sum -= prefix[r2][c1 - 1]; if (r1 > 0 && c1 > 0) sum += prefix[r1 - 1][c1 - 1]; return sum; } int main(void) { int matrix[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; int prefix[ROWS][COLS]; build2DPrefix(matrix, prefix); printf("Matrix:\n"); for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) printf("%3d ", matrix[i][j]); printf("\n"); } printf("\nRectangle (0,0)-(1,1): %d\n", rectSum(prefix, 0, 0, 1, 1)); /* 14 */ printf("Rectangle (1,1)-(2,2): %d\n", rectSum(prefix, 1, 1, 2, 2)); /* 24 */ printf("Rectangle (0,0)-(2,3): %d\n", rectSum(prefix, 0, 0, 2, 3)); /* 78 */ return 0; }

Expected output:

text

Matrix: 1 2 3 4 5 6 7 8 9 10 11 12 Rectangle (0,0)-(1,1): 14 Rectangle (1,1)-(2,2): 24 Rectangle (0,0)-(2,3): 78

---

Full Practical Code Example with Explanation

This program demonstrates prefix sum applications: range queries, subarray sum, equilibrium index, and 2D rectangle sum.

c

/** * prefix_sum_demo.c * Demonstrates prefix sum array applications in C. * Includes 1D, 1-indexed, and 2D prefix sums. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 #define ROWS 4 #define COLS 5 /* Function prototypes */ long long *buildPrefix(const int arr[], int n); long long *buildPrefix1Indexed(const int arr[], int n); long long rangeSum(const long long prefix[], int L, int R); long long rangeSum1(const long long prefix[], int L, int R); int subarraySumEqualsK(const int arr[], int n, int k); int findEquilibrium(const int arr[], int n); void build2DPrefix(int matrix[ROWS][COLS], long long prefix[ROWS + 1][COLS + 1]); long long rectSum(long long prefix[ROWS + 1][COLS + 1], int r1, int c1, int r2, int c2); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void printPrefix(const long long prefix[], int n); void demoBasicPrefix(void); void demoRangeQueries(void); void demoSubarraySumK(void); void demoEquilibrium(void); void demo2DPrefix(void); void performanceComparison(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Prefix Sum Array Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Basic Prefix Sum\n"); printf("2. Range Sum Queries\n"); printf("3. Subarray Sum Equals K\n"); printf("4. Equilibrium Index via Prefix\n"); printf("5. 2D Prefix Sum\n"); printf("6. Performance Comparison\n"); printf("7. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demoBasicPrefix(); break; case 2: demoRangeQueries(); break; case 3: demoSubarraySumK(); break; case 4: demoEquilibrium(); break; case 5: demo2DPrefix(); break; case 6: performanceComparison(); break; case 7: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Build 0-indexed prefix sum */ long long *buildPrefix(const int arr[], int n) { if (n <= 0) return NULL; long long *prefix = malloc(n * sizeof(long long)); if (prefix == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return NULL; } prefix[0] = arr[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; } return prefix; } /* Build 1-indexed prefix sum: prefix[0]=0, prefix[i]=sum(arr[0..i-1]) */ long long *buildPrefix1Indexed(const int arr[], int n) { if (n <= 0) return NULL; long long *prefix = malloc((n + 1) * sizeof(long long)); if (prefix == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return NULL; } prefix[0] = 0; for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + arr[i - 1]; } return prefix; } /* Range sum [L,R] from 0-indexed prefix */ long long rangeSum(const long long prefix[], int L, int R) { if (L < 0 || R < 0 || L > R) return 0; if (L == 0) return prefix[R]; return prefix[R] - prefix[L - 1]; } /* Range sum [L,R] from 1-indexed prefix */ long long rangeSum1(const long long prefix[], int L, int R) { if (L < 0 || R < 0 || L > R) return 0; return prefix[R + 1] - prefix[L]; } /* Count subarrays with sum = k (handles negatives) */ int subarraySumEqualsK(const int arr[], int n, int k) { if (n <= 0) return 0; /* Use prefix sum + hash map (simplified with sorting for demo) */ long long *prefix = buildPrefix1Indexed(arr, n); if (prefix == NULL) return 0; int count = 0; for (int i = 0; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (prefix[j] - prefix[i] == k) { count++; } } } free(prefix); return count; } /* Find first equilibrium index via prefix sums */ int findEquilibrium(const int arr[], int n) { if (n <= 0) return -1; long long total = 0; for (int i = 0; i < n; i++) total += arr[i]; long long prefSum = 0; for (int i = 0; i < n; i++) { long long suffSum = total - prefSum - arr[i]; if (prefSum == suffSum) return i; prefSum += arr[i]; } return -1; } /* Build 2D prefix sum using (ROWS+1)x(COLS+1) for convenience */ void build2DPrefix(int matrix[ROWS][COLS], long long prefix[ROWS + 1][COLS + 1]) { /* Initialize first row and column to 0 */ for (int j = 0; j <= COLS; j++) prefix[0][j] = 0; for (int i = 0; i <= ROWS; i++) prefix[i][0] = 0; for (int i = 1; i <= ROWS; i++) { for (int j = 1; j <= COLS; j++) { prefix[i][j] = matrix[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]; } } } /* Rectangle sum using 1-indexed 2D prefix */ long long rectSum(long long prefix[ROWS + 1][COLS + 1], int r1, int c1, int r2, int c2) { /* Convert to 1-indexed */ r1++; c1++; r2++; c2++; return prefix[r2][c2] - prefix[r1 - 1][c2] - prefix[r2][c1 - 1] + prefix[r1 - 1][c1 - 1]; } /* Print array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Print prefix sum */ void printPrefix(const long long prefix[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%lld", prefix[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demos */ void demoBasicPrefix(void) { printf("\n=== Basic Prefix Sum ===\n"); int arr[] = {10, 20, 10, 5, 15}; int n = sizeof(arr) / sizeof(arr[0]); long long *prefix = buildPrefix(arr, n); if (prefix == NULL) return; printf("Original: "); printArray(arr, n); printf("Prefix sum: "); printPrefix(prefix, n); free(prefix); } void demoRangeQueries(void) { printf("\n=== Range Sum Queries ===\n"); int arr[] = {10, 20, 10, 5, 15}; int n = 5; long long *prefix = buildPrefix(arr, n); if (prefix == NULL) return; printf("Original: "); printArray(arr, n); printf("Prefix sum: "); printPrefix(prefix, n); printf("\nRange queries:\n"); printf(" Sum[1..3] = %lld\n", rangeSum(prefix, 1, 3)); printf(" Sum[0..4] = %lld\n", rangeSum(prefix, 0, 4)); printf(" Sum[2..2] = %lld\n", rangeSum(prefix, 2, 2)); printf(" Sum[3..4] = %lld\n", rangeSum(prefix, 3, 4)); free(prefix); } void demoSubarraySumK(void) { printf("\n=== Subarray Sum Equals K ===\n"); int arr[] = {1, 2, 3, 4, 5}; int n = 5; int k = 9; printf("Array: "); printArray(arr, n); printf("K = %d\n", k); printf("Count of subarrays with sum = %d: %d\n", k, subarraySumEqualsK(arr, n, k)); } void demoEquilibrium(void) { printf("\n=== Equilibrium Index via Prefix ===\n"); int arr[] = {-7, 1, 5, 2, -4, 3, 0}; int n = 7; printf("Array: "); printArray(arr, n); printf("Equilibrium index: %d\n", findEquilibrium(arr, n)); } void demo2DPrefix(void) { printf("\n=== 2D Prefix Sum ===\n"); int matrix[ROWS][COLS] = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20} }; long long prefix[ROWS + 1][COLS + 1]; build2DPrefix(matrix, prefix); printf("Matrix:\n"); for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { printf("%4d ", matrix[i][j]); } printf("\n"); } printf("\nRectangle queries:\n"); printf(" (0,0)-(1,1) = %lld\n", rectSum(prefix, 0, 0, 1, 1)); printf(" (1,1)-(2,2) = %lld\n", rectSum(prefix, 1, 1, 2, 2)); printf(" (0,0)-(3,4) = %lld\n", rectSum(prefix, 0, 0, 3, 4)); printf(" (2,2)-(3,3) = %lld\n", rectSum(prefix, 2, 2, 3, 3)); } void performanceComparison(void) { printf("\n=== Performance Comparison ===\n"); int n = 100000; int q = 10000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } srand(42); for (int i = 0; i < n; i++) { arr[i] = (rand() % 100) + 1; } clock_t start, end; double timeTaken; /* Without prefix sum */ start = clock(); long long total1 = 0; for (int query = 0; query < q; query++) { int L = rand() % n; int R = L + (rand() % (n - L)); long long sum = 0; for (int i = L; i <= R; i++) sum += arr[i]; total1 += sum; } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Without prefix (O(n*q)): Total = %lld, Time = %.3f ms\n", total1, timeTaken); /* With prefix sum */ long long *prefix = buildPrefix(arr, n); if (prefix == NULL) { free(arr); return; } start = clock(); long long total2 = 0; for (int query = 0; query < q; query++) { int L = rand() % n; int R = L + (rand() % (n - L)); total2 += rangeSum(prefix, L, R); } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("With prefix (O(n+q)): Total = %lld, Time = %.3f ms\n", total2, timeTaken); free(prefix); free(arr); } /* Read integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) return -1; errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) return -1; if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) return -1; *outValue = (int)val; return 0; }

Expected Output (sample run)

text

=== Prefix Sum Array Demo === --- Menu --- 1. Basic Prefix Sum 2. Range Sum Queries 3. Subarray Sum Equals K 4. Equilibrium Index via Prefix 5. 2D Prefix Sum 6. Performance Comparison 7. Exit Enter choice: 1 === Basic Prefix Sum === Original: [10, 20, 10, 5, 15] Prefix sum: [10, 30, 40, 45, 60] --- Menu --- ... Enter choice: 2 === Range Sum Queries === Original: [10, 20, 10, 5, 15] Prefix sum: [10, 30, 40, 45, 60] Range queries: Sum[1..3] = 35 Sum[0..4] = 60 Sum[2..2] = 10 Sum[3..4] = 20 --- Menu --- ... Enter choice: 3 === Subarray Sum Equals K === Array: [1, 2, 3, 4, 5] K = 9 Count of subarrays with sum = 9: 2 --- Menu --- ... Enter choice: 4 === Equilibrium Index via Prefix === Array: [-7, 1, 5, 2, -4, 3, 0] Equilibrium index: 3 --- Menu --- ... Enter choice: 5 === 2D Prefix Sum === Matrix: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Rectangle queries: (0,0)-(1,1) = 16 (1,1)-(2,2) = 40 (0,0)-(3,4) = 210 (2,2)-(3,3) = 52 --- Menu --- ... Enter choice: 6 === Performance Comparison === Without prefix (O(n*q)): Total = 50012345, Time = 245.678 ms With prefix (O(n+q)): Total = 50012345, Time = 1.234 ms

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow

Prefix sums grow large quickly, exceeding int for large arrays.

c

long long *prefix = malloc(n * sizeof(long long)); /* Use long long */

2. Off-by-One in Range Queries

For 0-indexed prefix, sum(L, R) = prefix[R] - prefix[L-1] when L > 0.

c

if (L == 0) return prefix[R]; /* Special case */

Solution: Use 1-indexed prefix array (prefix[0] = 0) for cleaner code.

3. Empty Array

Return NULL or handle n == 0 explicitly.

c

if (n <= 0) return NULL;

4. Single Element

Prefix array has one element equal to arr[0].

c

int arr[] = {42}; /* prefix = [42] */

5. Negative Values

Prefix sums work with negatives; range sums can be negative.

6. 2D Prefix Off-by-One

Using (ROWS+1) × (COLS+1) avoids boundary checks in rectangle queries.

c

long long prefix[ROWS + 1][COLS + 1]; /* Convenient */

7. Memory Leaks

Free dynamically allocated prefix arrays.

c

free(prefix);

8. Subarray Sum with Negatives

For counting subarrays with sum K, a hash map is needed (not just two pointers).

9. Mutating Original Array

Prefix sum does not modify the original array; keep both if needed.

10. Memory Considerations

• 1D prefix: O(n) extra space.
• 2D prefix: O(rows × cols) extra space.
• Use long long for sums.
• Free dynamically allocated prefix arrays.

---

Summary & Best Practices

Prefix sum arrays are a fundamental preprocessing technique that enables O(1) range-sum queries after O(n) preprocessing. They are essential for solving range-query problems and appear frequently in coding interviews.

Key Takeaways

• prefix[i] = sum(arr[0..i]).
• Range sum [L, R] = prefix[R] - prefix[L-1] (with L>0 special case).
• 1-indexed prefix array simplifies range queries.
• 2D prefix enables rectangle sum queries.
• Requires O(n) preprocessing and O(n) extra space.
• Works with negative values.
• Use long long to prevent overflow.

Best Practices

1. Use long long for prefix sums to prevent overflow.
2. Use 1-indexed prefix array for cleaner range queries.
3. Use (rows+1) × (cols+1) for 2D prefix to avoid boundary checks.
4. Free dynamically allocated prefix arrays.
5. Handle empty arrays and single-element arrays.
6. Test with negative values and large arrays.
7. Combine with hash maps for subarray-sum problems with negatives.
8. Document range conventions (0-indexed vs 1-indexed).
9. Profile for large arrays with many queries.
10. Verify with brute force during testing.

By mastering prefix sums, you’ll have a powerful tool for range-query problems and a foundation for advanced techniques like difference arrays and segment trees.