Core Concepts

Difference arrays enable efficient range updates, while prefix sum arrays facilitate quick range queries.

Converting Original Array to Differnece Array

diff[i][j] = arr[i][j] - arr[i - 1][j] - arr[i][j - 1] + arr[i - 1][j - 1];

Reconstructing Original Array from Difference Array

arr[i][j] = diff[i][j] + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];

Querying Submatrix Sum Using Prefix Sums

int submatrixSum = prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1];

Applying Range Update with Difference Array

public static void applyUpdate(int[][] diff, int r1, int c1, int r2, int c2, int value) {
    diff[r1][c1] += value;
    diff[r1][c2 + 1] -= value;
    diff[r2 + 1][c1] -= value;
    diff[r2 + 1][c2 + 1] += value;
}

Example: Range Update Problem

This solution uses a difference array for batch updates, then reconstructs the final matrix.

import java.io.*;

public class RangeUpdateSolver {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter output = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static StreamTokenizer tokenizer = new StreamTokenizer(input);
    
    static int nextInt() throws IOException {
        tokenizer.nextToken();
        return (int) tokenizer.nval;
    }
    
    static int size, operations;
    static int[][] delta;
    
    static void updateRegion(int r1, int c1, int r2, int c2, int val) {
        delta[r1][c1] += val;
        delta[r1][c2 + 1] -= val;
        delta[r2 + 1][c1] -= val;
        delta[r2 + 1][c2 + 1] += val;
    }
    
    static void computeFinalMatrix() {
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                delta[i][j] += delta[i - 1][j] + delta[i][j - 1] - delta[i - 1][j - 1];
                output.print(delta[i][j] + " ");
            }
            output.println();
        }
        output.flush();
    }
    
    public static void main(String[] args) throws IOException {
        size = nextInt();
        operations = nextInt();
        delta = new int[size + 2][size + 2];
        
        for (int op = 0; op < operations; op++) {
            updateRegion(nextInt(), nextInt(), nextInt(), nextInt(), 1);
        }
        computeFinalMatrix();
    }
}

Example: Maximum Submatrix Sum

Constructs a 2D prefix sum aray to compute all possible submatrix sums efficiently.

import java.util.Scanner;

public class MaxSubmatrixSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int dimension = scanner.nextInt();
        int[][] prefix = new int[dimension + 1][dimension + 1];
        
        for (int i = 1; i <= dimension; i++) {
            for (int j = 1; j <= dimension; j++) {
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + scanner.nextInt();
            }
        }
        
        int maximum = Integer.MIN_VALUE;
        for (int startRow = 1; startRow <= dimension; startRow++) {
            for (int startCol = 1; startCol <= dimension; startCol++) {
                for (int endRow = startRow; endRow <= dimension; endRow++) {
                    for (int endCol = startCol; endCol <= dimension; endCol++) {
                        int currentSum = prefix[endRow][endCol] 
                                       - prefix[endRow][startCol - 1] 
                                       - prefix[startRow - 1][endCol] 
                                       + prefix[startRow - 1][startCol - 1];
                        maximum = Math.max(maximum, currentSum);
                    }
                }
            }
        }
        System.out.println(maximum);
    }
}

Example: Largest Square Submatrix of Ones

Uses prefix sums to verify if a square region contains all ones.

import java.io.*;
import java.util.Arrays;

public class MaxSquareOnes {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer parser = new StreamTokenizer(reader);
    
    static int nextInt() throws IOException {
        parser.nextToken();
        return (int) parser.nval;
    }
    
    public static void main(String[] args) throws IOException {
        int rows = nextInt();
        int cols = nextInt();
        int[][] cumulative = new int[rows + 1][cols + 1];
        
        Arrays.fill(cumulative[0], 0);
        for (int r = 1; r <= rows; r++) {
            cumulative[r][0] = 0;
        }
        
        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= cols; c++) {
                cumulative[r][c] = cumulative[r - 1][c] + cumulative[r][c - 1] 
                                  - cumulative[r - 1][c - 1] + nextInt();
            }
        }
        
        int maxSide = 0;
        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= cols; c++) {
                int maxPossible = Math.min(rows - r + 1, cols - c + 1);
                for (int side = 1; side <= maxPossible; side++) {
                    int endRow = r + side - 1;
                    int endCol = c + side - 1;
                    int regionSum = cumulative[endRow][endCol] 
                                  - cumulative[endRow][c - 1] 
                                  - cumulative[r - 1][endCol] 
                                  + cumulative[r - 1][c - 1];
                    if (regionSum == side * side) {
                        maxSide = Math.max(maxSide, side);
                    }
                }
            }
        }
        System.out.println(maxSide);
    }
}