Prefix sums and difference arrays
Precompute running totals once to answer any range-sum question in O(1), count subarrays with a target sum, sum rectangles in a grid, and apply range updates in O(1) with a difference array.
The prefix array
prefix[i] is the total of the first i items (prefix[0] is 0). Then the total of items l to r is everything up to r minus everything before l:
sum(a[l..r]) = prefix[r + 1] − prefix[l]
int[] a = { 3, 1, 4, 1, 5, 9, 2, 6 }; var prefix = new int[a.Length + 1]; // prefix[0] = 0for (int i = 0; i < a.Length; i++) prefix[i + 1] = prefix[i] + a[i];Console.WriteLine(string.Join(" ", prefix)); int RangeSum(int l, int r) => prefix[r + 1] - prefix[l];Console.WriteLine(RangeSum(2, 5)); // 4 + 1 + 5 + 9Console.WriteLine(RangeSum(0, 7)); // everything0 3 4 8 9 14 23 25 31 19 31
Prefix sums plus a dictionary
i to j has sum prefix[j + 1] − prefix[i]. So, walking left to right with a running sum, the number of runs ending here with sum k is the number of earlier prefix sums equal to sum − k. Keep those counts in a dictionary. Unlike the sliding window, this works with negative numbers too.
static int CountSubarrays(int[] a, int k){ var seen = new Dictionary<int, int> { [0] = 1 }; // prefix sum -> how many times int sum = 0, count = 0; foreach (int x in a) { sum += x; count += seen.GetValueOrDefault(sum - k); // runs ending here with sum k seen[sum] = seen.GetValueOrDefault(sum) + 1; } return count;} // [1, 2], [3], [2, 3, -2] and [3, -2, 2]Console.WriteLine(CountSubarrays(new[] { 1, 2, 3, -2, 2 }, 3));4
In two dimensions
P[r, c] holds the total of the rectangle from the top-left corner to just before (r, c). Any rectangle’s total is then four lookups: take the big rectangle, subtract the strip above and the strip to the left, and add back the corner that was subtracted twice.
int[,] g = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };int rows = 3, cols = 3; var P = new int[rows + 1, cols + 1];for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) P[r + 1, c + 1] = g[r, c] + P[r, c + 1] + P[r + 1, c] - P[r, c]; // total of rows 1..2, columns 1..2 (5 + 6 + 8 + 9)int s = P[3, 3] - P[1, 3] - P[3, 1] + P[1, 1];Console.WriteLine(s);28
The reverse trick: difference arrays
diff[start] += n and diff[end + 1] −= n. At the end, one running total over diff gives the real value for every day.
int days = 8;var diff = new int[days + 1]; // one extra slot for "end + 1" void AddCrew(int start, int end, int people){ diff[start] += people; // from start on: + people diff[end + 1] -= people; // from end + 1 on: back to before} AddCrew(1, 4, 2);AddCrew(3, 6, 5);AddCrew(0, 7, 1); var crew = new int[days];int running = 0;for (int d = 0; d < days; d++){ running += diff[d]; // a prefix sum rebuilds the values crew[d] = running;}Console.WriteLine(string.Join(" ", crew));1 3 3 8 8 6 6 1
PivotIndex(int[] a) that returns the first index where the sum of everything to its left equals the sum of everything to its right (the item itself is in neither), or −1. { 1, 7, 3, 6, 5, 6 } → 3 (1 + 7 + 3 = 11 = 5 + 6). { 1, 2, 3 } → −1. Use O(1) extra memory.
Show a hint
left sum, the right sum is total − left − a[i].
Show the solution
static int PivotIndex(int[] a){ int total = a.Sum(), left = 0; for (int i = 0; i < a.Length; i++) { if (left == total - left - a[i]) return i; left += a[i]; } return -1;} Console.WriteLine(PivotIndex(new[] { 1, 7, 3, 6, 5, 6 }));Console.WriteLine(PivotIndex(new[] { 1, 2, 3 }));3 -1
Remember
prefix[i]= total of the first i items; any range sum isprefix[r + 1] − prefix[l], O(1).Give the prefix array length n + 1 with a leading 0 to avoid special cases. Prefix sums + a dictionary count runs with a given sum, even with negative numbers. A difference array makes range updates O(1); a running total at the end rebuilds the values.