Prefix Sum
In this page:
Prefix Sum Idea
A prefix sum array stores, at each index i, the running total of all elements from the start up through i. Building it once in O(n) lets you answer many range-sum queries afterward almost instantly, instead of re-adding elements every time.
Example: Prefix Sum Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 4, 6, 8};
int n = 4;
int prefix[4];
prefix[0] = arr[0];
for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i]; // running total
cout << "prefix[2]: " << prefix[2] << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8};
int[] prefix = new int[4];
prefix[0] = arr[0];
for (int i = 1; i < 4; i++) prefix[i] = prefix[i - 1] + arr[i];
System.out.println("prefix[2]: " + prefix[2]);
}
}arr = [2, 4, 6, 8]
prefix = [arr[0]]
for x in arr[1:]:
prefix.append(prefix[-1] + x) # running total
print("prefix[2]:", prefix[2])#include <stdio.h>
int main() {
int arr[] = {2, 4, 6, 8};
int prefix[4];
prefix[0] = arr[0];
for (int i = 1; i < 4; i++) prefix[i] = prefix[i - 1] + arr[i];
printf("prefix[2]: %d\n", prefix[2]);
return 0;
}Login to try C/C++/Java code in the editor
Range Sum
To get the sum of elements from index l to r, you don't need to add them one by one: subtract the prefix sum just before l from the prefix sum at r, turning what would be an O(n) sum into an O(1) lookup.
Example: Range Sum
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int prefix[5];
prefix[0] = arr[0];
for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i];
int l = 1, r = 3;
int rangeSum = prefix[r] - (l > 0 ? prefix[l - 1] : 0); // O(1) lookup
cout << "Sum from " << l << " to " << r << ": " << rangeSum << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10};
int[] prefix = new int[5];
prefix[0] = arr[0];
for (int i = 1; i < 5; i++) prefix[i] = prefix[i - 1] + arr[i];
int l = 1, r = 3;
int rangeSum = prefix[r] - (l > 0 ? prefix[l - 1] : 0);
System.out.println("Sum from " + l + " to " + r + ": " + rangeSum);
}
}arr = [2, 4, 6, 8, 10]
prefix = [arr[0]]
for x in arr[1:]:
prefix.append(prefix[-1] + x)
l, r = 1, 3
range_sum = prefix[r] - (prefix[l - 1] if l > 0 else 0) # O(1) lookup
print(f"Sum from {l} to {r}:", range_sum)#include <stdio.h>
int main() {
int arr[] = {2, 4, 6, 8, 10};
int prefix[5];
prefix[0] = arr[0];
for (int i = 1; i < 5; i++) prefix[i] = prefix[i - 1] + arr[i];
int l = 1, r = 3;
int rangeSum = prefix[r] - (l > 0 ? prefix[l - 1] : 0);
printf("Sum from %d to %d: %d\n", l, r, rangeSum);
return 0;
}Login to try C/C++/Java code in the editor
Difference of Prefix Values
That subtraction trick, prefix[r] − prefix[l−1], is the whole idea behind prefix sums: any contiguous range's total can be recovered from just two precomputed values instead of scanning the range directly.
Example: Difference of Prefix Values
#include <iostream>
using namespace std;
int main() {
int prefix[] = {2, 6, 12, 20, 30};
int l = 2, r = 4;
// prefix[r] - prefix[l-1] recovers the range total from two lookups.
int total = prefix[r] - prefix[l - 1];
cout << "Range total: " << total << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] prefix = {2, 6, 12, 20, 30};
int l = 2, r = 4;
int total = prefix[r] - prefix[l - 1];
System.out.println("Range total: " + total);
}
}prefix = [2, 6, 12, 20, 30]
l, r = 2, 4
# prefix[r] - prefix[l-1] recovers the range total from two lookups.
total = prefix[r] - prefix[l - 1]
print("Range total:", total)#include <stdio.h>
int main() {
int prefix[] = {2, 6, 12, 20, 30};
int l = 2, r = 4;
int total = prefix[r] - prefix[l - 1];
printf("Range total: %d\n", total);
return 0;
}Login to try C/C++/Java code in the editor
Prefix Sum Applications
Beyond simple sums, the same technique extends to counting how many values in a range meet a condition, or comparing whether two ranges have equal totals, by building a prefix array over an appropriately transformed version of the data.
Example: Prefix Sum Applications
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 0, 1, 1, 0, 1};
int n = 6;
int prefixOnes[6];
prefixOnes[0] = arr[0];
for (int i = 1; i < n; i++) prefixOnes[i] = prefixOnes[i - 1] + arr[i]; // count of 1s so far
cout << "Count of 1s in [0..3]: " << prefixOnes[3] << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 0, 1, 1, 0, 1};
int[] prefixOnes = new int[6];
prefixOnes[0] = arr[0];
for (int i = 1; i < 6; i++) prefixOnes[i] = prefixOnes[i - 1] + arr[i];
System.out.println("Count of 1s in [0..3]: " + prefixOnes[3]);
}
}arr = [1, 0, 1, 1, 0, 1]
prefix_ones = [arr[0]]
for x in arr[1:]:
prefix_ones.append(prefix_ones[-1] + x) # count of 1s so far
print("Count of 1s in [0..3]:", prefix_ones[3])#include <stdio.h>
int main() {
int arr[] = {1, 0, 1, 1, 0, 1};
int prefixOnes[6];
prefixOnes[0] = arr[0];
for (int i = 1; i < 6; i++) prefixOnes[i] = prefixOnes[i - 1] + arr[i];
printf("Count of 1s in [0..3]: %d\n", prefixOnes[3]);
return 0;
}Login to try C/C++/Java code in the editor
Prefix Sum Practice
Prefix sums are cheap to build and pay off enormously when you need to answer many range queries on the same static array, turning an O(n) per-query cost into O(1) after a one-time O(n) setup.
Example: Prefix Sum Practice
#include <iostream>
using namespace std;
int main() {
// One-time O(n) build, then every range query answered in O(1).
int arr[] = {3, 1, 4, 1, 5, 9};
int n = 6;
int prefix[6];
prefix[0] = arr[0];
for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i];
cout << "Query [1,4]: " << prefix[4] - prefix[0] << endl;
cout << "Query [0,5]: " << prefix[5] << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9};
int[] prefix = new int[6];
prefix[0] = arr[0];
for (int i = 1; i < 6; i++) prefix[i] = prefix[i - 1] + arr[i];
System.out.println("Query [1,4]: " + (prefix[4] - prefix[0]));
System.out.println("Query [0,5]: " + prefix[5]);
}
}arr = [3, 1, 4, 1, 5, 9]
prefix = [arr[0]]
for x in arr[1:]:
prefix.append(prefix[-1] + x)
print("Query [1,4]:", prefix[4] - prefix[0])
print("Query [0,5]:", prefix[5])#include <stdio.h>
int main() {
int arr[] = {3, 1, 4, 1, 5, 9};
int prefix[6];
prefix[0] = arr[0];
for (int i = 1; i < 6; i++) prefix[i] = prefix[i - 1] + arr[i];
printf("Query [1,4]: %d\n", prefix[4] - prefix[0]);
printf("Query [0,5]: %d\n", prefix[5]);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: