Prefix Array

This is really simple, though I just did forget how to code one up.

ll prefix_sum(int l, int r) {
    if (l == 0) {
        return prefix[r];
    } else {
        return prefix[r] - prefix[l-1];
    }
}
 
// load in to array
for (int i=0;i<n;i++) {
	cin >> prefix[i];
}
for (int i=1;i<n;i++) {
	prefix[i] += prefix[i-1];
}

1-indexed prefix sums

ll prefix_sum(int l, int r) {
    return prefix[r+1] - prefix[l];
}
 
for (int i = 0;i<n;i++) {
cin >> arr[i];
}
 
for (int i = 0;i<n;i++) {
    prefix[i+1] = prefix[i] + arr[i];
}
 

2D prefix array

Use the Inclusion-Exclusion Principle:

$$S[i][j]=S[i][j-1]+S[i-1][j]-S[i-1][j-1]+A[i][j]$$

Setting the prefix sum

# Initialize
for i in range(n):
	for j in range(m):
		S[i][j] = A[i][j]
 
# Sweep along the x-axis
for i in range(1, n):
	for j in range(m):
		S[i][j] += S[i - 1][j]
 
# Sweep along the y-axis
for i in range(n):
	for j in range(1, m):
		S[i][j] += S[i][j - 1]

Parallelized Prefix Sum

Learned this through PMPP. Didn’t know it was possible, because it seems like sequential.

Related

• Difference Array