Prefix Sum Array Explained — Fast Range Queries in O(1) Time

package io.thecodeforge.algo;

import java.util.Arrays;

public class PrefixSumArray {

    private final long[] prefix;

    /**
     * Builds the prefix sum array in O(n).
     * Uses long to prevent integer overflow on large sums.
     */
    public PrefixSumArray(int[] arr) {
        prefix = new long[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
    }

    /**
     * Returns the sum of arr[l..r] inclusive. O(1).
     * @throws IllegalArgumentException if l > r or indices out of bounds
     */
    public long rangeSum(int l, int r) {
        if (l < 0 || r >= prefix.length - 1 || l > r) {
            throw new IllegalArgumentException(
                String.format("Invalid range [%d, %d] for array of length %d", l, r, prefix.length - 1)
            );
        }
        return prefix[r + 1] - prefix[l];
    }

    /**
     * Returns the total sum of the entire array. O(1).
     */
    public long totalSum() {
        return prefix[prefix.length - 1] - prefix[0];
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        PrefixSumArray ps = new PrefixSumArray(arr);

        System.out.println("Array: " + Arrays.toString(arr));
        System.out.println("Prefix: " + Arrays.toString(ps.prefix));
        System.out.println("sum(2..5) = " + ps.rangeSum(2, 5));  // 4+1+5+9 = 19
        System.out.println("sum(0..7) = " + ps.rangeSum(0, 7));  // 31
        System.out.println("sum(0..0) = " + ps.rangeSum(0, 0));  // 3
        System.out.println("sum(7..7) = " + ps.rangeSum(7, 7));  // 6
    }
}

package io.thecodeforge.algo;

import java.util.Arrays;

public class PrefixSum2D {

    private final long[][] prefix;

    /**
     * Builds the 2D prefix sum array in O(mn).
     * P[i][j] = sum of rectangle arr[0..i-1][0..j-1].
     */
    public PrefixSum2D(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        prefix = new long[rows + 1][cols + 1];

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                prefix[i][j] = matrix[i - 1][j - 1]
                    + prefix[i - 1][j]
                    + prefix[i][j - 1]
                    - prefix[i - 1][j - 1];
            }
        }
    }

    /**
     * Returns the sum of the rectangle from (r1,c1) to (r2,c2) inclusive. O(1).
     * Inclusion-exclusion: include bottom-right, exclude top row, exclude left column, add back corner.
     */
    public long rectangleSum(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];
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12}
        };

        PrefixSum2D ps = new PrefixSum2D(matrix);

        // Sum of entire matrix: 1+2+...+12 = 78
        System.out.println("Total sum: " + ps.rectangleSum(0, 0, 2, 3));

        // Sum of submatrix [1,1] to [2,2]: 6+7+10+11 = 34
        System.out.println("Submatrix [1,1..2,2]: " + ps.rectangleSum(1, 1, 2, 2));

        // Sum of top-left 2x2: 1+2+5+6 = 14
        System.out.println("Top-left 2x2: " + ps.rectangleSum(0, 0, 1, 1));

        // Single element: matrix[2][3] = 12
        System.out.println("Single element [2,3]: " + ps.rectangleSum(2, 3, 2, 3));
    }
}

package io.thecodeforge.algo;

import java.util.Arrays;

public class PrefixSumTrace {

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        int n = arr.length;

        long[] prefix = new long[n + 1];
        System.out.println("Building prefix sum array:");
        System.out.println("P[0] = 0 (sentinel)");

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
            System.out.printf("P[%d] = P[%d] + arr[%d] = %d + %d = %d%n",
                i + 1, i, i, prefix[i], arr[i], prefix[i + 1]);
        }

        System.out.println("\nPrefix array: " + Arrays.toString(prefix));

        // Trace queries
        int l = 2, r = 5;
        System.out.println("\nQuery sum(arr[" + l + ".." + r + "]):");
        System.out.println("  P[" + (r+1) + "] - P[" + l + "] = " + prefix[r+1] + " - " + prefix[l] + " = " + (prefix[r+1] - prefix[l]));
        System.out.println("  Verification: " + arr[2] + "+" + arr[3] + "+" + arr[4] + "+" + arr[5] + " = " + (arr[2]+arr[3]+arr[4]+arr[5]));

        l = 0; r = 7;
        System.out.println("\nQuery sum(arr[" + l + ".." + r + "]):");
        System.out.println("  P[" + (r+1) + "] - P[" + l + "] = " + prefix[r+1] + " - " + prefix[l] + " = " + (prefix[r+1] - prefix[l]));
    }
}

package io.thecodeforge.algo;

import java.util.Arrays;

public class DifferenceArray {

    private final long[] diff;
    private final int length;

    /**
     * Initializes a difference array from the original array.
     * D[0] = arr[0], D[i] = arr[i] - arr[i-1].
     */
    public DifferenceArray(int[] arr) {
        length = arr.length;
        diff = new long[length + 1]; // +1 for the r+1 boundary
        diff[0] = arr[0];
        for (int i = 1; i < length; i++) {
            diff[i] = arr[i] - arr[i - 1];
        }
    }

    /**
     * Adds value v to all elements in arr[l..r] inclusive. O(1).
     */
    public void rangeUpdate(int l, int r, long v) {
        diff[l] += v;
        if (r + 1 < diff.length) {
            diff[r + 1] -= v;
        }
    }

    /**
     * Reconstructs the final array by taking the prefix sum of the difference array. O(n).
     */
    public long[] getResult() {
        long[] result = new long[length];
        result[0] = diff[0];
        for (int i = 1; i < length; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] salaries = {50000, 60000, 55000, 70000, 45000};
        System.out.println("Original: " + Arrays.toString(salaries));

        DifferenceArray da = new DifferenceArray(salaries);

        // Give a $5000 raise to employees 1 through 3
        da.rangeUpdate(1, 3, 5000);
        System.out.println("After $5k raise to [1..3]: " + Arrays.toString(da.getResult()));

        // Apply a $2000 bonus to all employees (0 through 4)
        da.rangeUpdate(0, 4, 2000);
        System.out.println("After $2k bonus to all: " + Arrays.toString(da.getResult()));
    }
}

package io.thecodeforge.algo;

public class FenwickTree {

    private final long[] tree;
    private final int n;

    /**
     * Builds a Fenwick Tree from an array. O(n log n).
     * Supports point update and prefix sum query in O(log n).
     */
    public FenwickTree(int[] arr) {
        n = arr.length;
        tree = new long[n + 1];
        for (int i = 0; i < n; i++) {
            update(i, arr[i]);
        }
    }

    /**
     * Adds delta to arr[index]. O(log n).
     */
    public void update(int index, long delta) {
        for (int i = index + 1; i <= n; i += i & (-i)) {
            tree[i] += delta;
        }
    }

    /**
     * Returns the sum of arr[0..index] inclusive. O(log n).
     */
    public long prefixSum(int index) {
        long sum = 0;
        for (int i = index + 1; i > 0; i -= i & (-i)) {
            sum += tree[i];
        }
        return sum;
    }

    /**
     * Returns the sum of arr[l..r] inclusive. O(log n).
     */
    public long rangeSum(int l, int r) {
        return prefixSum(r) - (l > 0 ? prefixSum(l - 1) : 0);
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        FenwickTree ft = new FenwickTree(arr);

        System.out.println("sum(2..5) = " + ft.rangeSum(2, 5));  // 19
        System.out.println("sum(0..7) = " + ft.rangeSum(0, 7));  // 31

        // Update arr[3] from 1 to 10 (delta = +9)
        ft.update(3, 9);
        System.out.println("After update arr[3]+=9:");
        System.out.println("sum(2..5) = " + ft.rangeSum(2, 5));  // 4+10+5+9 = 28
        System.out.println("sum(0..7) = " + ft.rangeSum(0, 7));  // 40
    }
}