前缀和

前缀和可以快速求出数组中某一段连续区间的和

1. 一维前缀和

定义：对于数组 a，计算它的长为 n + 1 的前缀和数组 s，即 a 的前 0 个数的和，前 1 个数的和，前 2 个数的和……前 n 个数的和。

s[0] = 0
s[1] = a[0]
s[2] = a[0]+a[1]
  ⋮
s[i] = a[0]+a[1]+⋯+a[i−1]
  ⋮
s[n] = a[0]+a[1]+⋯+a[n−1]
例如：数组 a = [−2,0,3,−5,2,−1]，对应的前缀和数组 s = [0,−2,−2,1,−4,−2,−3]

int main() {
    vector<int> nums(n);
    vector<int> prefix(n + 1);
    for(int i = 1;i <= n;++i)
        // prefix[i] 表示（0）到（i）的和
        prefix[i] = nums[i - 1] + prefix[i - 1];
    // [l, r]区间和：
    cout << prefix[r] - prefix[l - 1] << endl;
}

2. 二维前缀和

算法讲解：

int main() {
    vector<vector<int>> nums(n, vector<int>(m));
    vector<vector<long long>> prefix(n + 1, vector<long long>(m + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            // 计算二维前缀和：prefix[i][j] 表示 (0, 0) 到 (i-1, j-1) 的和
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + nums[i - 1][j - 1];

    int x1, y1, x2, y2;
    cout << prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1] << endl;
}

在实际做题中，要明确数组含义，不能死记模板。

差分

对于数组 a，定义其差分数组（difference array）为

d[i]=

• a[0],i = 0
• a[i]−a[i−1],i >= 1 ​

1. 性质 1：从左到右累加 d 中的元素，可以得到数组 a。
2. 性质 2：如下两个操作是等价的。

• 把 a 的子数组 a[i], a[i+1] , ... , a[j] 都加上 x
• 把 d[i] 增加 x，把 d[j+1] 减少 x

例如：数组 a=[1,3,3,5,8]，对其中的相邻元素两两作差（右边减左边），得到数组 [2,0,2,3]。然后在开头补上 a[0]，得到差分数组 d=[1,2,0,2,3]