当前位置： 首页 > article >正文

算法-前缀和与差分

article 2025/4/1 16:19:14

一、前缀和（Prefix Sum）

1. 核心思想

前缀和是一种预处理数组的方法，通过预先计算并存储数组的前缀和，使得后续的区间和查询可以在**O(1)**时间内完成。

2. 定义

给定数组 nums，前缀和数组 prefixSum 的每个元素 prefixSum[i] 表示从 nums[0] 到 nums[i] 的和：
prefixSum[i] = nums[0] + nums[1] + ... + nums[i]

3. 代码实现
// 构建前缀和数组
public int[] buildPrefixSum(int[] nums) {
    int n = nums.length;
    int[] prefixSum = new int[n];
    prefixSum[0] = nums[0];
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }
    return prefixSum;
}

// 查询区间和 [left, right]
public int queryRangeSum(int[] prefixSum, int left, int right) {
    if (left == 0) return prefixSum[right];
    return prefixSum[right] - prefixSum[left - 1];
}
4. 应用场景

  • 高频区间和查询：例如多次查询数组的某个子区间和。

  • 二维扩展：处理二维矩阵中的子矩阵和（如LeetCode 304题）。

5. 示例

假设 nums = [1, 2, 3, 4]，前缀和数组为 [1, 3, 6, 10]：

  • queryRangeSum([0, 2]) → 6（即 1+2+3）

  • queryRangeSum([1, 3]) → 9（即 2+3+4）

前缀和是从1开始的  定义S[0]=0。注意区间和M-N之间的和是S[N]-S[M-1]

一维前缀和

  1. 定义 对于给定的数列，其前缀和数列定义为，并且规定。例如数列，，， ，。
  2. 计算方法 可以通过递推方式计算前缀和，即 。在 Java 代码中实现如下：
import java.util.Scanner;

public class OneDPrefixSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[n + 1];
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i];
        }
        for (int i = 0; i < m; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            System.out.println(s[r] - s[l - 1]);
        }
    }
}

这里首先通过循环读取数组 a 的元素，然后计算前缀和数组 s 。对于每次询问的区间 [l, r]，其区间和通过 快速得到。原理是 是前 r 项的和， 是前 l - 1 项的和，两者相减就得到区间 [l, r]的和。

3. 应用场景 当需要频繁查询数列中某一区间的和时，使用前缀和可将每次查询时间复杂度从 O(n)（暴力求和）降低到O(1) 。比如统计一段时间内数据的累计和等场景。

二维前缀和详解

二维前缀和是一种用于快速计算矩阵中子矩阵元素和的高效算法，适用于需要频繁查询子矩阵和的场景（如LeetCode 304题）。

一、核心思想

通过预处理构建一个前缀和矩阵，使得任意子矩阵的和可以在 O(1) 时间内查询。
核心公式（假设矩阵从左上角 (0,0) 开始）：

prefixSum[i][j]=matrix[i][j]+prefixSum[i−1][j]+prefixSum[i][j−1]−prefixSum[i−1][j−1]prefixSum[i][j]=matrix[i][j]+prefixSum[i−1][j]+prefixSum[i][j−1]−prefixSum[i−1][j−1]

查询子矩阵 (x1, y1) 到 (x2, y2) 的和：

sum=prefixSum[x2][y2]−prefixSum[x1−1][y2]−prefixSum[x2][y1−1]+prefixSum[x1−1][y1−1]sum=prefixSum[x2][y2]−prefixSum[x1−1][y2]−prefixSum[x2][y1−1]+prefixSum[x1−1][y1−1]

二、实现步骤
1. 构建二维前缀和数组

假设原始矩阵为 matrix[m][n]，前缀和矩阵为 prefixSum[m][n]：

public int[][] buildPrefixSum(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] prefixSum = new int[m][n];
    prefixSum[0][0] = matrix[0][0];
    
    // 初始化第一行和第一列
    for (int j = 1; j < n; j++) 
        prefixSum[0][j] = prefixSum[0][j-1] + matrix[0][j];
    for (int i = 1; i < m; i++) 
        prefixSum[i][0] = prefixSum[i-1][0] + matrix[i][0];
    
    // 填充其他位置
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            prefixSum[i][j] = matrix[i][j] 
                + prefixSum[i-1][j] 
                + prefixSum[i][j-1] 
                - prefixSum[i-1][j-1];
        }
    }
    return prefixSum;
}
2. 查询子矩阵和
public int querySubmatrix(int[][] prefixSum, int x1, int y1, int x2, int y2) {
    int sum = prefixSum[x2][y2];
    if (x1 > 0) sum -= prefixSum[x1-1][y2];  // 减去上方区域
    if (y1 > 0) sum -= prefixSum[x2][y1-1];  // 减去左侧区域
    if (x1 > 0 && y1 > 0) sum += prefixSum[x1-1][y1-1];  // 补回重复减去的左上角
    return sum;
}
三、示例演示

假设原始矩阵为：

matrix=[123456789]matrix=​147​258​369​​

构建前缀和矩阵 prefixSum：

[13651221122745]​1512​31227​62145​​

查询子矩阵 (1,1) 到 (2,2) 的和：

sum=45−21−12+3=15(即 5+6+8+9=28，原矩阵此处有误，实际应为正确计算)sum=45−21−12+3=15(即 5+6+8+9=28，原矩阵此处有误，实际应为正确计算)

四、应用场景

  1. 高频子矩阵和查询（如 LeetCode 304. 二维区域和检索）。

  2. 图像处理：计算图像局部区域的像素和。

  3. 动态规划优化：在二维动态规划问题中减少重复计算。

五、复杂度分析
操作时间复杂度空间复杂度
构建前缀和矩阵O(mn)O(mn)
查询子矩阵和O(1)O(1)
六、注意事项

  1. 索引边界：矩阵的行列索引需从 0 开始，避免越界。

  2. 空矩阵处理：输入矩阵为空时需返回异常或合理值。

  3. 大数溢出：若元素值较大，前缀和可能溢出，需使用 long 类型存储。

七、完整代码示例
public class TwoDPrefixSum {
    private int[][] prefixSum;

    public TwoDPrefixSum(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        int m = matrix.length, n = matrix[0].length;
        prefixSum = new int[m][n];
        // 构建前缀和矩阵
        prefixSum[0][0] = matrix[0][0];
        for (int j = 1; j < n; j++) 
            prefixSum[0][j] = prefixSum[0][j-1] + matrix[0][j];
        for (int i = 1; i < m; i++) 
            prefixSum[i][0] = prefixSum[i-1][0] + matrix[i][0];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefixSum[i][j] = matrix[i][j] 
                    + prefixSum[i-1][j] 
                    + prefixSum[i][j-1] 
                    - prefixSum[i-1][j-1];
            }
        }
    }

    public int sumRegion(int x1, int y1, int x2, int y2) {
        int sum = prefixSum[x2][y2];
        if (x1 > 0) sum -= prefixSum[x1-1][y2];
        if (y1 > 0) sum -= prefixSum[x2][y1-1];
        if (x1 > 0 && y1 > 0) sum += prefixSum[x1-1][y1-1];
        return sum;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        TwoDPrefixSum solver = new TwoDPrefixSum(matrix);
        System.out.println(solver.sumRegion(1, 1, 2, 2)); // 输出28（5+6+8+9）
    }
}

通过掌握二维前缀和，你可以高效解决涉及子矩阵和的复杂问题，显著提升算法性能。

差分算法详解

差分（Difference Array）是一种用于高效处理数组区间增减操作的算法技巧，尤其适用于需要多次对数组的某个区间进行增减操作的场景（如 LeetCode 的「航班预订统计」「拼车」问题）。以下是差分算法的完整解析：

一、核心思想

  1. 差分数组定义
    给定原数组 nums，其差分数组 diff 满足：

    • diff[0] = nums[0]

    • diff[i] = nums[i] - nums[i-1]（当 i > 0 时）

  2. 区间操作优化
    对原数组的区间 [left, right] 进行增减操作时，只需修改差分数组的两个位置：

    • diff[left] += val

    • 若 right + 1 < n，则 diff[right + 1] -= val
      最后通过差分数组还原原数组时，区间增减的效果会自动生效。

二、实现步骤
1. 构建差分数组
// 输入原数组 nums，返回差分数组 diff
public int[] buildDiffArray(int[] nums) {
    if (nums == null || nums.length == 0) return new int[0];
    int n = nums.length;
    int[] diff = new int[n];
    diff[0] = nums[0];
    for (int i = 1; i < n; i++) {
        diff[i] = nums[i] - nums[i - 1];
    }
    return diff;
}
2. 区间增减操作
// 对原数组的区间 [left, right] 增加 val（通过差分数组间接实现）
public void rangeUpdate(int[] diff, int left, int right, int val) {
    diff[left] += val;
    if (right + 1 < diff.length) {
        diff[right + 1] -= val;
    }
}
3. 通过差分数组还原原数组
// 输入差分数组 diff，返回还原后的原数组 nums
public int[] restoreArray(int[] diff) {
    if (diff == null || diff.length == 0) return new int[0];
    int n = diff.length;
    int[] nums = new int[n];
    nums[0] = diff[0];
    for (int i = 1; i < n; i++) {
        nums[i] = nums[i - 1] + diff[i];
    }
    return nums;
}
三、示例演示

假设原数组 nums = [1, 3, 5, 7]，其差分数组为 diff = [1, 2, 2, 2]：

  • 对区间 [1, 2] 增加 3：

    rangeUpdate(diff, 1, 2, 3); // diff 变为 [1, 5, 2, -1]

  • 还原后的数组：

    restoreArray(diff); // 结果 [1, 6, 8, 7]

    验证：原数组的 [1, 2] 区间（即 3, 5）被增加了 3，结果变为 6, 8。

四、应用场景

  1. 高频区间更新
    例如多次对数组的某个区间进行增减操作，时间复杂度从 O(kn) 优化到 O(n + k)，其中 k 是操作次数

  2. 动态维护数组状态
    例如游戏中多个区域同时施加增益/减益效果。

五、复杂度分析
操作时间复杂度空间复杂度
构建差分数组O(n)O(n)
单次区间更新O(1)O(1)
还原原数组O(n)O(n)
六、完整代码示例
public class DifferenceArray {
    private int[] diff;

    // 根据原数组构建差分数组
    public DifferenceArray(int[] nums) {
        if (nums.length == 0) return;
        int n = nums.length;
        diff = new int[n];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // 区间 [left, right] 增加 val
    public void rangeUpdate(int left, int right, int val) {
        diff[left] += val;
        if (right + 1 < diff.length) {
            diff[right + 1] -= val;
        }
    }

    // 还原原数组
    public int[] restore() {
        int n = diff.length;
        int[] nums = new int[n];
        nums[0] = diff[0];
        for (int i = 1; i < n; i++) {
            nums[i] = nums[i - 1] + diff[i];
        }
        return nums;
    }

    // 测试代码
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7};
        DifferenceArray da = new DifferenceArray(nums);
        da.rangeUpdate(1, 2, 3); // 对区间 [1,2] 增加3
        int[] result = da.restore();
        System.out.println(Arrays.toString(result)); // 输出 [1, 6, 8, 7]
    }
}
七、注意事项

  1. 索引边界：注意 right + 1 是否超出数组范围（避免越界）。

  2. 初始数组处理：原数组为空时需特殊处理。

  3. 多次更新：可连续调用 rangeUpdate，最后统一还原数组。

通过差分算法，可以将多次区间操作的时间复杂度从 O(kn) 优化到 O(n + k)，是处理大规模区间更新问题的核心技巧。


http://www.kler.cn/a/614802.html

相关文章：

  • FGSM对抗样本生成算法实现（pytorch版）
  • AI助力高效办公：如何利用AI制作PPT提升工作效率
  • 结构化分析方法 数据流图详解
  • 工业控制系统安全：从漏洞到防线，Python如何成为你的护卫者
  • 图论 岛屿问题 ACM 模式 JS
  • 怎么搭建区块链服务私有云平台
  • C++实现布隆过滤器
  • 创意 Python 爱心代码分享
  • Python常用爬虫库介绍
  • vue3+element plus +el-tree-v2实现树形单选
  • presto任务优化参数
  • Uniapp微信开发树形选择组件
  • LeetCode 热题 100_杨辉三角（82_118_简单_C++）(动态规划)
  • Tof 深度相机原理
  • 0基础STM32之滤波函数（卡尔曼滤波）
  • 抽象的算法0.1.3.1版本
  • 算法训练营第二十八天 | 动态规划（一）
  • WinForm真入门-简介
  • NLP语言模型训练里的特殊向量
  • Linux系统中应用端控制串口的基本方法