PreComputation Technique on Arrays
Last Updated :
21 Dec, 2023
Precomputation refers to the process of pre-calculating and storing the results of certain computations or data structures(array in this case) in advance, in order to speed up the execution time of a program. This can be useful in situations where the same calculations are needed multiple times, as it avoids the need to recalculate them every time.
This technique relies on fast retreival of already stored data rather than recalculation.
Some Common Pre-Computation Techniques used on Array:
Though pre-computation can be done in various ways over a wide range of questions, in this section we will look at some of the popular techniques of pre-computation:
Prefix/Suffix on 1-D Array:
A prefix array PRE[] is defined on an array ARR[], such that for each index 'i' PRE[i] stores the information about the values from ARR[0] to ARR[i]. This information can be in the form of prefix sum, prefix max, prefix gcd, etc.
Let's construct prefix array for ARR[] = {4, 2, 1, -1, 3}, to do this we can simply iterate ARR[] from 0 to size-1, and store PRE[i]=ARR[i]+PRE[i-1], after doing this we have PRE[] = {4, 6, 7, 6, 9}
Why do we need this Prefix Array?
- For simplicity consider the example for Prefix Sum Array. Suppose we have an array ARR[] of size N, and Q queries and for each query, we have to output the sum of values between the index L to R.
- The Brute Force way of doing this will result in a time complexity of O(N*Q) where we iterate from L to R in each query to know the sum. In order to improve this time complexity we can use Pre-Computation i.e. calculate the Prefix sum array before processing the queries, and then for each query simply return PRE[R]-PRE[L-1] as the result in O(1), the overall complexity then would be O(max(N, Q))
- The Suffix array is similar to the Prefix array the only difference is that the Suffix array stores the information about the values from index 'i' to the end of the array rather that start of the array i..e. SUFFIX[i] stores information about values from ARR[i] to ARR[size-1].
Below is the code to construct a Prefix Sum and Suffix Sum array:
C++
#include <iostream>
using namespace std;
// This function prints the array
void print(int arr[], int N)
{
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// This function calculates the PrefixSum
// of the array
void PrefixSum(int ARR[], int N)
{
// PRE[] array stores the result
int PRE[N];
for (int i = 0; i < N; i++) {
// At index 0, no previous values
// are present
if (i == 0)
PRE[i] = ARR[i];
else
PRE[i] = PRE[i - 1] + ARR[i];
}
cout << "Prefix Sum: ";
print(PRE, N);
}
// This function finds the Suffix
// sum of the array
void SuffixSum(int ARR[], int N)
{
// This array stores the result
int SUF[N];
for (int i = N - 1; i >= 0; i--) {
// At index N-1, there is no suffix
// value available
if (i == N - 1)
SUF[i] = ARR[i];
else
SUF[i] = SUF[i + 1] + ARR[i];
}
cout << "Suffix Sum: ";
print(SUF, N);
}
// Driver code
int main()
{
int N = 5;
int ARR[N] = { 4, 2, 1, -1, 3 };
cout << "Given Array: ";
print(ARR, N);
// Funtion call to calculate prefix sum
PrefixSum(ARR, N);
// Function call to calculate suffix sum
SuffixSum(ARR, N);
return 0;
}
public class PrefixSuffixSum {
// This function prints the array
static void print(int[] arr, int N) {
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// This function calculates the PrefixSum of the array
static void prefixSum(int[] arr, int N) {
// PRE[] array stores the result
int[] PRE = new int[N];
for (int i = 0; i < N; i++) {
// At index 0, no previous values are present
if (i == 0)
PRE[i] = arr[i];
else
PRE[i] = PRE[i - 1] + arr[i];
}
System.out.print("Prefix Sum: ");
print(PRE, N);
}
// This function finds the Suffix sum of the array
static void suffixSum(int[] arr, int N) {
// This array stores the result
int[] SUF = new int[N];
for (int i = N - 1; i >= 0; i--) {
// At index N-1, there is no suffix value available
if (i == N - 1)
SUF[i] = arr[i];
else
SUF[i] = SUF[i + 1] + arr[i];
}
System.out.print("Suffix Sum: ");
print(SUF, N);
}
// Driver code
public static void main(String[] args) {
int N = 5;
int[] ARR = { 4, 2, 1, -1, 3 };
System.out.print("Given Array: ");
print(ARR, N);
// Function call to calculate prefix sum
prefixSum(ARR, N);
// Function call to calculate suffix sum
suffixSum(ARR, N);
}
}
//This code is contriuted by chinmaya121221
# This function prints the array
def print_array(arr, N):
for i in range(N):
print(arr[i], end = " ")
print()
# This function calculates the PrefixSum
# of the array
def PrefixSum(ARR, N):
# PRE[] array stores the result
PRE = [0] * N
for i in range(N):
# At index 0, no previous values
# are present
if (i == 0):
PRE[i] = ARR[i]
else:
PRE[i] = PRE[i - 1] + ARR[i]
print("Prefix Sum: ", end = "")
print_array(PRE, N)
# This function finds the Suffix
# sum of the array
def SuffixSum(ARR, N):
# This array stores the result
SUF = [0] * N
for i in range(N - 1, -1, -1):
# At index N-1, there is no suffix
# value available
if (i == N - 1):
SUF[i] = ARR[i]
else:
SUF[i] = SUF[i + 1] + ARR[i]
print("Suffix Sum: ", end = "")
print_array(SUF, N)
# Driver code
if __name__ == "__main__":
N = 5
ARR = [4, 2, 1, -1, 3]
print("Given Array: ", end = "")
print_array(ARR, N)
# Funtion call to calculate prefix sum
PrefixSum(ARR, N)
# Function call to calculate suffix sum
SuffixSum(ARR, N)
using System;
class Program
{
// This function prints the array
static void Print(int[] arr, int N)
{
for (int i = 0; i < N; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
// This function calculates the PrefixSum of the array
static void PrefixSum(int[] ARR, int N)
{
// PRE array stores the result
int[] PRE = new int[N];
for (int i = 0; i < N; i++)
{
// At index 0, no previous values are present
if (i == 0)
PRE[i] = ARR[i];
else
PRE[i] = PRE[i - 1] + ARR[i];
}
Console.Write("Prefix Sum: ");
Print(PRE, N);
}
// This function finds the Suffix sum of the array
static void SuffixSum(int[] ARR, int N)
{
// SUF array stores the result
int[] SUF = new int[N];
for (int i = N - 1; i >= 0; i--)
{
// At index N-1, there is no suffix value available
if (i == N - 1)
SUF[i] = ARR[i];
else
SUF[i] = SUF[i + 1] + ARR[i];
}
Console.Write("Suffix Sum: ");
Print(SUF, N);
}
static void Main()
{
int N = 5;
int[] ARR = { 4, 2, 1, -1, 3 };
Console.Write("Given Array: ");
Print(ARR, N);
// Function call to calculate prefix sum
PrefixSum(ARR, N);
// Function call to calculate suffix sum
SuffixSum(ARR, N);
}
}
// This function prints the array
function print(arr, N) {
for (let i = 0; i < N; i++) {
console.log(arr[i] + " ");
}
console.log();
}
// This function calculates the PrefixSum
// of the array
function PrefixSum(ARR, N) {
// PRE[] array stores the result
let PRE = [];
for (let i = 0; i < N; i++) {
// At index 0, no previous values
// are present
if (i === 0)
PRE[i] = ARR[i];
else
PRE[i] = PRE[i - 1] + ARR[i];
}
console.log("Prefix Sum: ");
print(PRE, N);
}
// This function finds the Suffix
// sum of the array
function SuffixSum(ARR, N) {
// This array stores the result
let SUF = [];
for (let i = N - 1; i >= 0; i--) {
// At index N-1, there is no suffix
// value available
if (i === N - 1)
SUF[i] = ARR[i];
else
SUF[i] = SUF[i + 1] + ARR[i];
}
console.log("Suffix Sum: ");
print(SUF, N);
}
// Driver code
let N = 5;
let ARR = [4, 2, 1, -1, 3];
console.log("Given Array: ");
print(ARR, N);
PrefixSum(ARR, N);
SuffixSum(ARR, N);
OutputGiven Array: 4 2 1 -1 3
Prefix Sum: 4 6 7 6 9
Suffix Sum: 9 5 3 2 3
Prefix on 2-D Array:
The above idea of Prefix on 1-D array can be expanded to 2-D array, where we have a 2-D array ARR[][] of size NxM and PRE[i][j] will store the information about the values from row 0 to 'i' and and column 0 to 'j' . Let's say we want to retrieve the sum of values of submatrice [i1, j1] to [i2, j2], we can simply use our 2-D prefix sum array to achieve this by simple Inclusion Exclusion principle PRE[i2][j2] - PRE[i2][j1-1] - PRE[i1-1][j2] + PRE[i1-1][j1-1].
Below is the code construct prefix sum for 2-D array:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
void print(vector<vector<int> >& arr, int N, int M)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
}
void PrefixSum(vector<vector<int> >& ARR, int N, int M)
{
vector<vector<int> > PRE(N, vector<int>(M));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int x = 0;
int y = 0;
int z = 0;
if (i - 1 >= 0)
x = PRE[i - 1][j];
if (j - 1 >= 0)
y = PRE[i][j - 1];
if (i - 1 >= 0 && j - 1 >= 0)
z = PRE[i - 1][j - 1];
PRE[i][j] = ARR[i][j] + x + y - z;
}
}
cout << "Give Array:" << endl;
print(ARR, N, M);
cout << "Prefix Sum Array:" << endl;
print(PRE, N, M);
}
// Drivers code
int main()
{
int N = 4;
int M = 4;
vector<vector<int> > ARR = { { 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 } };
// Function Call
PrefixSum(ARR, N, M);
return 0;
}
import java.util.Arrays;
public class PrefixSum {
// Function to print a 2D array
static void print(int[][] arr, int N, int M)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
// Function to compute the prefix sum of a 2D array
static void prefixSum(int[][] arr, int N, int M)
{
int[][] pre = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int x = 0, y = 0, z = 0;
if (i - 1 >= 0)
x = pre[i - 1][j];
if (j - 1 >= 0)
y = pre[i][j - 1];
if (i - 1 >= 0 && j - 1 >= 0)
z = pre[i - 1][j - 1];
pre[i][j] = arr[i][j] + x + y - z;
}
}
System.out.println("Given Array:");
print(arr, N, M);
System.out.println("Prefix Sum Array:");
print(pre, N, M);
}
// Driver code
public static void main(String[] args)
{
int N = 4;
int M = 4;
int[][] arr = { { 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 } };
// Function call
prefixSum(arr, N, M);
}
}
def print_matrix(matrix):
# Function to print a 2D array
for row in matrix:
print(" ".join(map(str, row)))
def prefix_sum(matrix, n, m):
# Function to compute the prefix sum of a 2D array
prefix = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
x = 0 if i - 1 < 0 else prefix[i - 1][j]
y = 0 if j - 1 < 0 else prefix[i][j - 1]
z = 0 if i - 1 < 0 or j - 1 < 0 else prefix[i - 1][j - 1]
prefix[i][j] = matrix[i][j] + x + y - z
print("Given Array:")
print_matrix(matrix)
print("Prefix Sum Array:")
print_matrix(prefix)
if __name__ == "__main__":
N = 4
M = 4
matrix = [
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]
]
# Function call
prefix_sum(matrix, N, M)
# This code is contributed by shivamgupta0987654321
using System;
class Program {
// Function to print a 2D array
static void Print(int[, ] arr, int N, int M)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Console.Write(arr[i, j] + " ");
}
Console.WriteLine();
}
}
// Function to compute the prefix sum of a 2D array
static void PrefixSum(int[, ] ARR, int N, int M)
{
int[, ] PRE = new int[N, M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int x = 0;
int y = 0;
int z = 0;
// Calculate the sum of elements above the
// current element
if (i - 1 >= 0)
x = PRE[i - 1, j];
// Calculate the sum of elements to the left
// of the current element
if (j - 1 >= 0)
y = PRE[i, j - 1];
// Calculate the sum of elements in the
// diagonal (top-left)
if (i - 1 >= 0 && j - 1 >= 0)
z = PRE[i - 1, j - 1];
// Compute the prefix sum for the current
// element
PRE[i, j] = ARR[i, j] + x + y - z;
}
}
// Print the given array
Console.WriteLine("Given Array:");
Print(ARR, N, M);
// Print the computed prefix sum array
Console.WriteLine("Prefix Sum Array:");
Print(PRE, N, M);
}
// Driver code
static void Main()
{
int N = 4;
int M = 4;
int[, ] ARR = { { 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 } };
// Function Call
PrefixSum(ARR, N, M);
}
}
function print(arr) {
for (let i = 0; i < arr.length; i++) {
console.log(arr[i].join(' '));
}
console.log();
}
function calculatePrefixSum(ARR) {
const N = ARR.length;
const M = ARR[0].length;
// Initialize the prefix sum array
const PRE = new Array(N);
for (let i = 0; i < N; i++) {
PRE[i] = new Array(M).fill(0);
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
let x = 0;
let y = 0;
let z = 0;
if (i - 1 >= 0)
x = PRE[i - 1][j];
if (j - 1 >= 0)
y = PRE[i][j - 1];
if (i - 1 >= 0 && j - 1 >= 0)
z = PRE[i - 1][j - 1];
PRE[i][j] = ARR[i][j] + x + y - z;
}
}
console.log("Given Array:");
print(ARR);
console.log("Prefix Sum Array:");
print(PRE);
}
// Driver's code
const N = 4;
const M = 4;
const ARR = [
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]
];
// Function Call
calculatePrefixSum(ARR);
OutputGive Array:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Prefix Sum Array:
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
Hashing the Arrays data:
There are times when Hashing can be used for pre-computation and drastically reduce the time complexity of program. Suppose for various query we would require the first index of an element 'e' in the array. Instead of calculating this again and again, we can simply iterate on array once and hash the element to the first index it occurs to and finally retrieve this value in O(1) for each query.
Moreover Hashing can be combined with other precomputation techniques like prefix_sum in order to enhance the usability.
Practice Problems:
Similar Reads
PreComputation Technique on Arrays
Precomputation refers to the process of pre-calculating and storing the results of certain computations or data structures(array in this case) in advance, in order to speed up the execution time of a program. This can be useful in situations where the same calculations are needed multiple times, as
15 min read
Queries for the product of first N factorials
Given Q[] queries where each query consists of an integer N, the task is to find the product of first N factorials for each of the query. Since the result could be large, compute it modulo 109 + 7.Examples: Input: Q[] = {4, 5} Output: 288 34560 Query 1: 1! * 2! * 3! * 4! = 1 * 2 * 6 * 24 = 288 Query
7 min read
Range sum queries without updates
Given an array arr of integers of size n. We need to compute the sum of elements from index i to index j. The queries consisting of i and j index values will be executed multiple times. Examples: Input : arr[] = {1, 2, 3, 4, 5} i = 1, j = 3 i = 2, j = 4Output : 9 12 Input : arr[] = {1, 2, 3, 4, 5} i
6 min read
Range Queries for Frequencies of array elements
Given an array of n non-negative integers. The task is to find frequency of a particular element in the arbitrary range of array[]. The range is given as positions (not 0 based indexes) in array. There can be multiple queries of given type. Examples: Input : arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11}; lef
13 min read
Count Primes in Ranges
Given a 2d array queries[][] of size n, where each query queries[i] contain 2 elements [l, r], your task is to find the count of number of primes in inclusive range [l, r] Examples: Input: queries[][] = [ [1, 10], [5, 10], [11, 20] ]Output: 4 2 4Explanation: For query 1, number of primes in range [1
12 min read
Check in binary array the number represented by a subarray is odd or even
Given an array such that all its terms is either 0 or 1.You need to tell the number represented by a subarray a[l..r] is odd or even Examples : Input : arr = {1, 1, 0, 1} l = 1, r = 3 Output : odd number represented by arr[l...r] is 101 which 5 in decimal form which is odd Input : arr = {1, 1, 1, 1}
4 min read
GCDs of given index ranges in an Array
Given an array arr[] of size N and Q queries of type {qs, qe} where qs and qe denote the starting and ending index of the query, the task is to find the GCD of all the numbers in the range. Examples: Input: arr[] = {2, 3, 60, 90, 50};Index Ranges: {1, 3}, {2, 4}, {0, 2}Output: GCDs of given ranges a
14 min read
Mean of range in array
Given an array arr[] of n integers and q queries represented by an array queries[][], where queries[i][0] = l and queries[i][1] = r. For each query, the task is to calculate the mean of elements in the range l to r and return its floor value. Examples: Input: arr[] = [3, 7, 2, 8, 5] queries[][] = [[
12 min read
Difference Array | Range update query in O(1)
You are given an integer array arr[] and a list of queries. Each query is represented as a list of integers where: [1, l, r, x]: Adds x to all elements from arr[l] to arr[r] (inclusive).[2]: Prints the current state of the array.You need to perform the queries in order. Examples : Input: arr[] = [10
11 min read
Range sum query using Sparse Table
We have an array arr[]. We need to find the sum of all the elements in the range L and R where 0 <= L <= R <= n-1. Consider a situation when there are many range queries. Examples: Input : 3 7 2 5 8 9 query(0, 5) query(3, 5) query(2, 4) Output : 34 22 15Note : array is 0 based indexed and q
8 min read