Prefix Sums

int[] nums = {1, 3, -2, 4, 5};
int n = nums.length;
int[] prefix = new int[n + 1]; // prefix[0] = 0
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
// prefix = [0, 1, 4, 2, 6, 11]

// Range sum [l, r] (0-indexed, inclusive)
int rangeSum(int l, int r) {
    return prefix[r + 1] - prefix[l];
}
// sum(1, 3) = prefix[4] - prefix[1] = 6 - 1 = 5
// = nums[1] + nums[2] + nums[3] = 3 + (-2) + 4 = 5 ✓

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    freq.put(0, 1); // empty prefix has sum 0
    int count = 0, prefixSum = 0;

    for (int num : nums) {
        prefixSum += num;
        // We need prefixSum - k to have appeared before
        count += freq.getOrDefault(prefixSum - k, 0);
        freq.merge(prefixSum, 1, Integer::sum);
    }
    return count;
}

// Find index where left sum == right sum
public int pivotIndex(int[] nums) {
    int total = Arrays.stream(nums).sum();
    int leftSum = 0;
    for (int i = 0; i < nums.length; i++) {
        // rightSum = total - leftSum - nums[i]
        if (leftSum == total - leftSum - nums[i]) return i;
        leftSum += nums[i];
    }
    return -1;
}

int[][] grid = {{1,2,3},{4,5,6},{7,8,9}};
int m = grid.length, n = grid[0].length;
int[][] prefix = new int[m+1][n+1];

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        prefix[i][j] = grid[i-1][j-1]
            + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];

// Sum of sub-rectangle (r1,c1) to (r2,c2) (0-indexed)
int rectSum(int r1, int c1, int r2, int c2) {
    return prefix[r2+1][c2+1]
         - prefix[r1][c2+1]
         - prefix[r2+1][c1]
         + prefix[r1][c1];
}