Prefix sums enable efficient range sum computations by precomputing cumulative values, reducing query time to O(1). This technique is widely used for optimizing array and matrix operations.

import java.util.Scanner;

public class ArraySumOptimizer {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int size = scanner.nextInt();
            int queries = scanner.nextInt();
            int[] input = new int[size + 1];
            for (int idx = 1; idx <= size; idx++) {
                input[idx] = scanner.nextInt();
            }
            long[] cumulative = new long[size + 1];
            for (int idx = 1; idx <= size; idx++) {
                cumulative[idx] = cumulative[idx - 1] + input[idx];
            }
            for (int i = 0; i < queries; i++) {
                int start = scanner.nextInt();
                int end = scanner.nextInt();
                System.out.println(cumulative[end] - cumulative[start - 1]);
            }
        }
    }
}

To two-dimensional grids, a prefix sum matrix computes submatirx sums efficiently using incluison-exclusion principles. Each cell stores the sum from the top-left corner to its position.

import java.util.Scanner;

public class MatrixSumCalculator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int rows = scanner.nextInt();
        int cols = scanner.nextInt();
        int queryCount = scanner.nextInt();
        int[][] matrix = new int[rows + 1][cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        long[][] prefix = new long[rows + 1][cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i][j];
            }
        }
        for (int i = 0; i < queryCount; i++) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            long total = prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1];
            System.out.println(total);
        }
    }
}

Identifying the pivot index where left and right sums are equal uses separate cumulative arrays for left and right sides.

public class PivotIndexFinder {
    public int findPivot(int[] data) {
        int len = data.length;
        int[] leftSums = new int[len];
        int[] rightSums = new int[len];
        for (int i = 1; i < len; i++) {
            leftSums[i] = leftSums[i - 1] + data[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            rightSums[i] = rightSums[i + 1] + data[i + 1];
        }
        for (int i = 0; i < len; i++) {
            if (leftSums[i] == rightSums[i]) return i;
        }
        return -1;
    }
}

Computing products of all elements except current one leverages prefix and suffix product arrays for O(n) time complexity.

public class ProductExceptSelf {
    public int[] compute(int[] values) {
        int n = values.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        prefix[0] = 1;
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * values[i - 1];
        }
        suffix[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * values[i + 1];
        }
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] * suffix[i];
        }
        return result;
    }
}