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];
}

Parallelized Prefix Sum

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