Prefix Sum Array - Efficient Approach

PHOTO EMBED

Mon Feb 07 2022 14:28:06 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #arrays #prefixsum

import java.util.*;
import java.io.*;

class GFG 
{ 
	// For preprocessing : O(n)
    static int[] preSum(int arr[], int n)
    {	
    	int prefix_sum[] = new int[n];

    	prefix_sum[0] = arr[0];

    	for(int i = 1; i < n; i++)
    	{
    		prefix_sum[i] = prefix_sum[i - 1] + arr[i];
    	}
    	
    	return prefix_sum;
    }

	// For answer queries : O(1)
    static int getSum(int prefix_sum[], int l, int r)
    {
    	if(l != 0)
    		return prefix_sum[r] - prefix_sum[l - 1];
    	else
    		return prefix_sum[r];
    }
    
    public static void main(String args[]) 
    { 
       int arr[] = {2, 8, 3, 9, 6, 5, 4}, n = 7;

       int prefix_sum[] = preSum(arr, n);

       System.out.println(getSum(prefix_sum, 1, 3));
       
       System.out.println(getSum(prefix_sum, 0, 2));
       
    } 

}
content_copyCOPY

Given an array arr[] of size n, its prefix sum array is another array prefixSum[] of the same size, such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] … arr[i]. Examples : Input : arr[] = {10, 20, 10, 5, 15} Output : prefixSum[] = {10, 30, 40, 45, 60} Explanation : While traversing the array, update the element by adding it with its previous element. prefixSum[0] = 10, prefixSum[1] = prefixSum[0] + arr[1] = 30, prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on. --------------------------------------------------------------------------------------------------------- I/P : arr[] = {2, 8, 3, 9, 6, 5, 4} Queries : getSum(0, 2) // l, r getSum(1, 3) getSum(2, 6) O/P : 13, 20, 27