Prefix Sum
Prefix sums are a way to make finding the sum of any subarray fast. A prefix sum array stores the sum of all the elements up to each index in the original array.
Original Array:
nums = [2, 4, 1, 8, 3]
Prefix Sum Array:
prefix = [2, 6, 7, 15, 18]
Here’s how you generate the prefix sum array:
prefix[0] = nums[0] = 2
prefix[1] = nums[0] + nums[1] = 2 + 4 = 6
prefix[2] = nums[0] + nums[1] + nums[2] = 2 + 4 + 1 = 7
prefix[3] = nums[0] + nums[1] + nums[2] + nums[3] = 2 + 4 + 1 + 8 = 15
prefix[4] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] = 2 + 4 + 1 + 8 + 3 = 18
How to Use Prefix Sums to Find Subarray Sums
Let’s say you want to find the sum of the subarray from index i
to j
in the original array.
The sum of that subarray is prefix[j]  prefix[i  1]
.
Example 1:
 Subarray from index
i = 1
toj = 3
:[4, 1, 8]
 Its sum is
4 + 1 + 8 = 13
 Using prefix sums:
prefix[3]  prefix[0] = 15  2 = 13
Example 2:
 Subarray from index
i = 2
toj = 4
:[1, 8, 3]
 Its sum is
1 + 8 + 3 = 12
 Using prefix sums:
prefix[4]  prefix[1] = 18  6 = 12
Special Case for i = 0
If i = 0
, you would get an outofbounds index when you try to access prefix[1]
. To handle this, you can either:
 Use
0
asprefix[1]
 Or use the expression
prefix[j]  prefix[i] + nums[i]
That’s how prefix sums help you quickly find the sum of any subarray.
The last two columns were blank because they were meant to be placeholders for any specific example you might want to calculate. However, I understand that could be confusing, so let’s fill those in with the example calculations:
Index  Original Array (nums )  Prefix Sum Array (prefix )  Sum from index i to j  Calculation Using Prefix Sum 

0  2  2     
1  4  6  13 (i=1, j=3)  prefix[3]  prefix[0] = 15  2 = 13 
2  1  7  12 (i=2, j=4)  prefix[4]  prefix[1] = 18  6 = 12 
3  8  15     
4  3  18     
In this revised table, I’ve filled in the last two columns to show how you can use prefix sums to calculate the sum of the subarray from index i
to j
. I used the examples of summing from i=1
to j=3
and from i=2
to j=4
.
The variables i
and j
represent the starting and ending indices of the subarray in the original array nums
that you want to find the sum of. In the examples:
i=1, j=3
means you’re interested in the subarray that starts at index 1 and ends at index 3, which is[4, 1, 8]
in the original arraynums
.i=2, j=4
means you’re interested in the subarray that starts at index 2 and ends at index 4, which is[1, 8, 3]
in the original arraynums
.
These subarrays include the elements at both the starting index i
and the ending index j
.
Prefix Sum 1D Array
Description
Given an array of integers, the task is to calculate the Prefix Sum. The Prefix Sum is an array derived from the original array where the value at each position i
is the sum of the first i
numbers in the original array.
Java
In Java, you can calculate the Prefix Sum by iterating through the array and adding each element to the sum of the previous elements.


C++
In C++, you can calculate the Prefix Sum in a similar way by iterating through the array.


Python
In Python, you can also calculate the Prefix Sum by iterating through the list.


These examples cover calculating the Prefix Sum for an array of integers in Java, C++, and Python. They build a new array where each value is the sum of the original array’s values up to that index.
Tabular Representation
Here’s a table that demonstrates the calculation of the prefix sum for the input array [10, 20, 30, 40]
.
Iteration  Current Element  Prefix Sum So Far  Resulting Prefix Sum Array 

0  10  10  [10, , , ] 
1  20  30  [10, 30, , ] 
2  30  60  [10, 30, 60, ] 
3  40  100  [10, 30, 60, 100] 
Explanation:
 Iteration 0: The first element is 10, so the prefix sum is 10.
 Iteration 1: The next element is 20, so the prefix sum is 10 + 20 = 30.
 Iteration 2: The next element is 30, so the prefix sum is 10 + 20 + 30 = 60.
 Iteration 3: The next element is 40, so the prefix sum is 10 + 20 + 30 + 40 = 100.
The resulting prefix sum array is [10, 30, 60, 100]
, which represents the sum of all elements in the array up to each corresponding position.
Prefix Sum 2D Array
Description
The concept of Prefix Sum for a 2D array is a powerful and efficient technique often used to perform multiple queries on a grid, such as the sum of elements within a subgrid. It works by precomputing a new 2D array where each cell (i, j)
represents the sum of all the elements from the topleft corner (0, 0)
to the current cell (i, j)
. This allows for calculating the sum of any subgrid in constant time after the precomputation step.
Solution
Below are the explanations and code snippets for creating a Prefix Sum array for a given 2D array in Java, C++, and Python.
Java
In Java, you can create the Prefix Sum array by iterating over the original array and adding the values based on the previous rows and columns.


C++
Similarly, in C++, you iterate over the array and accumulate the sums based on the previous rows and columns.


Python
In Python, you can achieve the same by following a similar approach using list comprehension.


The implementation in all three languages involves two nested loops that iterate through the original grid. The value of the prefix sum at any cell (i, j)
is calculated based on the values in the original grid and the previously computed cells in the prefix sum grid. This makes the computation efficient and allows for quick querying of subgrid sums later on.
Visual Representation
Let’s take a simple 2D array as an example to illustrate the concept of Prefix Sum for a 2D array.
Original Array (Before)
Suppose we have the following 3x3 grid:
4 2 3
1 5 7
3 6 2
Prefix Sum Array (After)
By applying the prefix sum technique as described earlier, we will compute the following 3x3 grid:
4 6 9
5 12 22
8 21 34
Explanation
Here’s how we computed the Prefix Sum Array:
 First cell
(0, 0)
remains the same as in the original array:4
.  Second cell
(0, 1)
is the sum of original cells(0, 0)
and(0, 1)
:4 + 2 = 6
.  Third cell
(0, 2)
is the sum of original cells(0, 0)
,(0, 1)
, and(0, 2)
:4 + 2 + 3 = 9
.  Fourth cell
(1, 0)
is the sum of original cells(0, 0)
,(1, 0)
:4 + 1 = 5
.  Fifth cell
(1, 1)
is the sum of original cells(0, 0)
,(0, 1)
,(1, 0)
, and(1, 1)
:4 + 2 + 1 + 5 = 12
.  And so on, until the entire prefix sum array is computed.
The prefix sum array allows us to quickly determine the sum of any subgrid within the original array. For example, the sum of the values in the subgrid from (1, 1)
to (2, 2)
in the original array is 5 + 7 + 6 + 2 = 20
, which can be computed in constant time using the prefix sum array.
Prefix Sum for Binary Tree
Prefix Sum for a binary tree allows us to precompute sums for various sections of the tree so that we can answer sum queries (e.g., sum of values along a particular path or within a certain subtree) more efficiently.
The Prefix Sum is computed by performing a DepthFirst Traversal (DFS) of the tree, where for each node, we add its value to the sum of its parent’s prefix sum. This process continues recursively for all nodes, and the final result gives us the sum from the root to every node in the tree.
The Prefix Sum for a binary tree can be very helpful in scenarios where we want to query sums of values along certain paths or within specific subtrees multiple times.
Solution
Java Code


C++ Code


Python Code


These code snippets traverse the binary tree and calculate the prefix sum for each node. The prefix sum at any given node represents the sum of all the values from the root node to that particular node in the tree. This information can later be used to answer various types of sumrelated queries efficiently.
Prefix sum is a powerful technique that can be used to preprocess an array to facilitate fast queries on sum of elements in particular subarrays, without modifying the original array. With the help of prefix sums, we can compute sums over subarrays in constant time.
How to Compute Prefix Sum:
Create a new array prefixSum of the same size as the original array. prefixSum[0] = originalArray[0] For every index i from 1 to n1, prefixSum[i] = prefixSum[i1] + originalArray[i]
C++ Implementation:


Benefits of Prefix Sum:
Quickly find the sum of any subarray using just two array lookups. Helps in reducing the time complexity of summing over subarrays from O(n) to O(1).
Few questions to practice: https://leetcode.com/tag/prefixsum/ https://leetcode.com/problems/maximumsumof3nonoverlappingsubarrays/ https://leetcode.com/problems/continuoussubarraysum/ https://leetcode.com/problems/subarraysumequalsk/ https://leetcode.com/problems/maximumsizesubarraysumequalsk/ https://leetcode.com/problems/numberofsubmatricesthatsumtotarget/ https://leetcode.com/problems/maxsumofrectanglenolargerthank/ https://leetcode.com/problems/binarysubarrayswithsum/ https://leetcode.com/problems/pathsumiii/ https://leetcode.com/problems/subarraysumsdivisiblebyk/ https://leetcode.com/problems/rangesumquery2dimmutable/ https://leetcode.com/problems/countnumberofnicesubarrays/ https://leetcode.com/problems/matrixblocksum/ https://leetcode.com/problems/rangesumofsortedsubarraysums/ https://leetcode.com/problems/findtwononoverlappingsubarrayseachwithtargetsum/ https://leetcode.com/problems/rangesumqueryimmutable/ https://leetcode.com/problems/stonegamevii/ https://leetcode.com/problems/maximumpointsyoucanobtainfromcards/ https://leetcode.com/problems/minimumoperationstoreducextozero/ https://leetcode.com/problems/defusethebomb/ https://leetcode.com/problems/maxsumofrectanglenolargerthank/ https://leetcode.com/problems/maximumsidelengthofasquarewithsumlessthanorequaltothreshold/ https://leetcode.com/problems/waystomakeafairarray/ https://leetcode.com/problems/minimummovestomakearraycomplementary/ https://leetcode.com/problems/waystosplitarrayintothreesubarrays/ https://leetcode.com/problems/sumofabsolutedifferencesinasortedarray/ https://leetcode.com/problems/maximumerasurevalue/ https://leetcode.com/problems/canmakepalindromefromsubstring/ https://leetcode.com/problems/makesumdivisiblebyp/ https://leetcode.com/problems/maximumabsolutesumofanysubarray/ https://leetcode.com/problems/numberofwonderfulsubstrings/