Casey

20250305-前缀和与差分

最近更新：2025-03-05 | 字数总计：200 | 阅读估时：1分钟 | 阅读量：2次

前缀和与差分互为逆操作，其都是认为构造的、用于简化的方法，以下从构造方法和作用两个方面来看这两个操作。

前缀和

对于一个数组，其前缀和定义为。在代码中，为了便于计算，通常将数组 a[] 从序号 1 开始存储，并令 a[0] = 0，前缀和数组的构造方式如下。

vector<int> s(a.size(), 0);
for (int i = 1; i < s.size(); i++) {
  s[i] = s[i - 1] + a[i];
}

一维前缀和的作用在于快速求出数组 a[] 在某一区间 [i,j] 的和，为 a[j] - a[i - 1]。

二维前缀和类似于一维前缀和，但其构造与作用的对象为二维矩阵。

2025-03-05 该篇文章被 Casey 打上标签: 算法归为分类: 学习