前缀和与差分 Java实现

class PreSum1 {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();//m次求和操作
        int n = scanner.nextInt();
        int[] nums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            nums[i] = scanner.nextInt();
        }

        
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i]; //sum[i] = nums[0] + nums[1] + ... + nums[i]
        }

        for (int i = 0; i < m; i++) { //m次操作
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            //这里直接输出  对于其他题目 可能会用sum数组进行一系列操作
            System.out.println(sum[r] - sum[l - 1]);
        }
    }
}

class PreSum2 {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[][] nums = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                nums[i][j] = scanner.nextInt();
            }
        }

        //构造二维前缀和数组sum
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i][j]; //sum[1][1] = nums[1][1];
            }
        }

        for (int i = 0; i < k; i++) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            //通过计算公式得到(x1,y1)-(x2,y2)子矩阵的元素之和
            System.out.println(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);
        }
    }
}

class PreSub1 {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[] nums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            nums[i] = scanner.nextInt();
        }

        //构造差分数组
        int[] sub = new int[n + 1];
        for (int i = 1; i <= n; i++) { //这里sub[1] = nums[1]  即差分数组第一个元素值为原数组第一个元素值
            sub[i] = nums[i] - nums[i - 1];
        }

        for (int i = 0; i < m; i++) { //m次操作
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            int c = scanner.nextInt();
            sub[l] += c;
            sub[r + 1] -= c;
        }

        for (int i = 1; i <= n; i++) {
            nums[i] = nums[i - 1] + sub[i];//还原nums数组
            System.out.print(nums[i] + " ");
        }

    }
}

class PreSub2 {
    

    static int[][] sub; 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[][] nums = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                nums[i][j] = scanner.nextInt();
            }
        }

        //构造差分数组
        sub = new int[m + 2][n + 2];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //两种构造差分数组的方法
                insert(i, j, i, j, nums[i][j]);//法一  借用insert()函数
                // sub[i][j]=nums[i][j] - nums[i-1][j] - nums[i][j-1] + nums[i-1][j-1] 直接构造方法
            }
        }

        for (int i = 0; i < k; i++) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            int c = scanner.nextInt();
            //对差分数组进行操作
            insert(x1, y1, x2, y2, c);
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sub[i][j] += sub[i - 1][j] + sub[i][j - 1] - sub[i - 1][j - 1];
                nums[i][j] = sub[i][j];//得到变化后的数组
                System.out.print(nums[i][j] + " ");
            }
            System.out.println();
        }
    }

    static void insert(int x1, int y1, int x2, int y2, int c) {
        sub[x1][y1] += c;
        sub[x2 + 1][y1] -= c;
        sub[x1][y2 + 1] -= c;
        sub[x2 + 1][y2 + 1] += c;
    }
}