前缀和与差分数组 - YHT's Note Repo

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 一维前缀和数组 ## 前缀和数组的定义给定数组 `arr`，其**前缀和数组**的定义有两种方式。 - 方式一：`prefix_sum[i]` 表示数组 `arr` 中**区间 `[0, i]` 的前缀和**（**前`i+1`项**元素之和） - 方式二：`prefix_sum[i]` 表示数组 `arr` 中**区间 `[0, i)` 的前缀和**（**==前`i` 项==** 元素之和） - 特别的，有 **==哨兵边界== `prefix_sum[0]`** 表示 0 项元素之和，即为 0. 如下图所示： ![[Excalidraw-Solution/前缀和与差分数组_1.excalidraw.svg|839]] %%[[Excalidraw-Solution/前缀和与差分数组_1.excalidraw.md|🖋 Edit in Excalidraw]]%% 方式二相较于方式一的优点在于 "**统一了区间和的计算逻辑**" ： - 第一种方式中，**计算 "区间和" 时需要先==判断左边界 `l` 是否为`0`==**，对应不同逻辑； - 第二种方式中，`[l, r]` 的**区间和** 统一为 `prefix_sum[r + 1] - prefix_sum[l]` 。 ## 前缀和数组的构建 ### 定义方式一 - `prefix_sum[i]` 表示数组 `arr` 中**区间 `[0, i]` 的前缀和**（**前`i+1`项**元素之和） - `prefix_sum` 长度为 `n`； - 构建前缀和数组： - `prefix_sum[0] = arr[0]`； - `prefix_sum[i] = prefix_sum[i - 1] + arr[i]`，对 `i = [1, n-1]` - `[l, r]` 的区间和为：（需要分类讨论 `l==0` 与 `l!=0` ） - `if l == 0`，即为`prefix_sum[l]`； - `if l != 0`，则为 `prefix_sum[r] - prefix_sum[l-1]`； ```cpp // 前缀和数组 // 定义一: `prfixe_sum[i]` 表示下标区间 `[0, i]` 的前 `i+1` 项元素之和 class PrefixSumArray { public: PrefixSumArray(const std::vector<int> arr) { if (!arr.empty()) { prefix_sum.resize(arr.size()); prefix_sum[0] = arr[0]; for (size_t i = 1; i < arr.size(); ++i) { prefix_sum[i] = prefix_sum[i - 1] + arr[i]; } } } // 求区间和: [l, r]之和. int RangeSum(int l, int r) const { if (l == 0) return prefix_sum[r]; // [0, r] return prefix_sum[r] - prefix_sum[l - 1]; // [l, r] } private: std::vector<int> prefix_sum; }; ``` ### 定义方式二 - `prefix_sum[i]` 表示数组 `arr` 中**区间 `[0, i)` 的前缀和**（**前`i` 项**元素之和） - `prefix_sum` 长度为 `n + 1`； - 构建前缀和数组： - `prefix[0] = 0`； - `prefix[i + 1] = prefix[i] + arr[i]`，对 `i = [0, n-1]` ； - 求区间和： - `[l, r]` 的区间和为 `prefix_sum[r + 1] - prefix_sum[l]` > [!NOTE] 优点：`prefix_sum[0] == 0` 相当于哨兵 > > - 统一了初始化逻辑：对 `i` 从`[0, n-1]` 有 `prefix_sum[i + 1] = prefix_sum[i] + nums[i]`； > - 统一了求 "区间和" 的逻辑，对于区间 `[l, r]` 无需分类讨论 `l==0`的情况。 ```cpp // 前缀和数组 // 定义二: `prfixe_sum[i]` 表示下标区间 `[0, i)` 的前 `i` 项元素之和 class PrefixSumArray2 { public: // 构建前缀和数组 PrefixSumArray2(const std::vector<int> arr) { if (!arr.empty()) { prefix_sum.resize(arr.size() + 1); // n + 1 prefix_sum[0] = 0; // 首项为0 for (size_t i = 0; i < arr.size(); ++i) { prefix_sum[i + 1] = prefix_sum[i] + arr[i]; } } } // 返回区间[l, r]之和. int RangeSum(int l, int r) const { return prefix_sum[r+1] - prefix_sum[l - 1]; } private: std::vector<int> prefix_sum; }; ``` ## 前缀和数组的应用总结 1. **计算前缀和** - **前 i 项元素之和**； - **最大/最小 k 项元素之和**（为有序数组构建前缀和数组） 2. **计算区间和** 3. 计算数轴上**一组坐标点==两两之间距离==的==总和==** $O(n)$ 4. ...... > [!summary] "前缀和" 的应用 > > "**前缀和**"（更确切的说，某种前缀状态）的应用主要分为两类： > > - 目标区间范围已知时，要求**查询指定区间的状态**； > - 目标区间范围未知时，要求**找出满足条件的目标区间**； > > 对于上述两类题目，部分场景下还需要先进行预处理：将一些**特定的区间状态**需要先**转换为明确的 "==位置标记 (`-1/0/1`)==" 进行==建模==**，从而能够通过 "**==区间和==**" 来对**区间状态**进行表达。 > ^zaj9km ## 前缀和数组的基本应用——利用大小前缀和之差计算 "区间和" 区间 `[l, r]` 的 **==区间和==** = **大前缀区间`[0, r]` 与小前缀区间 `[0, l]` 的==前缀和之差==** 由此，通过预先处理得到一个 "**前缀和数组/累加数组**"，可实现**对任意 "==区间和==" 的 $O(1)$ 查询**。 #### 利用前缀和求"环形数组"上的区间和求**环形数组**上的区间和 `[l, r]`：将**区间边界下标`l`、`r`** 映射为**原数组上的有效下标 `l_ori`、`r_ori`**，有两种可能情况： 1. 若 `l_ori <= r_ori`： - 区间 `[l, r]` -> 原数组上 **==单段==区间**： `[l_ori, r_ori]`； 2. 若 `l_ori > r_ori`： - 区间 `[l, r]` -> 原数组上 **==首尾两段==区间**： `[0, r_ori]` & `[l_ori, n) 因此，分类讨论，如下所示： ```cpp // 返回环形数组上的区间[l, r]之和. int RangeSumInCircularArray(vector<int>& prefix_sum, int l, int r) { int n = prefix_sum.size() - 1; // 将边界下标映射为原数组中的下标 int l_ori = (l%n+n)%n; int r_ori = (r%n+n)%n; if (l_ori <= r_ori) { return prefix_sum[r_ori+1] - prefix_sum[l_ori]; } else { return prefix_sum[r_ori+1] + prefix_sum[n] - prefix_sum[l_ori]; } } ``` #### 利用前缀和数组求区间中的字符频次 ```cpp // 构造前缀和数组, 记录字符频次. vector<vector<int>> prefix_sum(26, vector<int>(n + 1, 0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < 26; ++j) { prefix_sum[j][i + 1] = prefix_sum[j][i]; } ++prefix_sum[s[i] - 'a'][i + 1]; } ``` ## 前缀和数组的扩展应用 ### 前缀和 & 二分查找 ##### （1）为数组中每个元素获取其左右侧"最远"的 "更大/更小元素" - 构建**前/后缀状态数组**，记录 **==前/后缀序列中的最小值 or 最大值==**； - 为数组中每项元素`arr[i]`，在**前/后缀数组上==二分查找==**。 | 查找目标 | 所需构建的前后缀数组 | 二分查找目标 | | -------------------- | ----------- | ------------------- | | 左侧 "最远" 的 "更**小**元素" | 前缀**最小值**数组 | `<arr[i]` 的**首**项元素 | | 左侧 "最远" 的 "更**大**元素" | 前缀**最大值**数组 | `>arr[i]` 的**首**项元素 | | 右侧 "最远" 的 "更**小**元素" | 后缀**最小值**数组 | `<arr[i]` 的**尾**项元素 | | 右侧 "最远" 的 "更**大**元素" | 后缀**最大值**数组 | `>arr[i]` 的**尾**项元素 | ![[Excalidraw-Solution/前缀和与差分数组_2.excalidraw.svg|455]] %%[[Excalidraw-Solution/前缀和与差分数组_2.excalidraw.md|🖋 Edit in Excalidraw]]%% # 一维后缀和数组后缀和数组只存在**一种有效定义**：**`suffix[i]` 表示区间 `[i, n-1]` 的后缀和**。区分后缀和数组长度设置为 `n` 与 `n + 1` 两种情况： ##### 后缀和数组长度为 n ```cpp // 构建后缀和数组 vector<int> suffix(n); suffix[n-1] = arr[n-1]; for (int i = n - 2; i >= 0; --i) { suffix[i] = suffix[i + 1] + arr[i]; } // 利用后缀和计算[l, r]区间和 void range(int l, int r, vector<int>& suffix) { if (r == n) return suffix[l]; return suffix[l] - suffix[r + 1]; } ``` ##### 后缀和数组长度为 n+1 ```cpp // 构建后缀和数组 vector<int> suffix(n + 1); suffix[n] = 0; // 最后一项初始化为0, 用作哨兵. for (int i = n - 1; i >= 0; --i) { suffix[i] = suffix[i-1] + arr[i]; } // 利用后缀和计算[l, r]区间和 void range(int l, int r, vector<int>& suffix) { return suffix[l] - suffix[r + 1]; // 无需再讨论r == n-1的情况. } ``` # 前后缀数组不同定义方式的应用差异示例 ##### 示例一参见 [[99-题解/leetcode/lc-2865 美丽塔 I#思路二：应用两次单调栈|lc-2865 美丽塔 I#思路二：应用两次单调栈]] 前后缀数组长度定义为 `n + 1`： ```cpp // 思路二: // 写法一: 前缀和数组长度定义为n+1 class Solution { public: long long maximumSumOfHeights(vector<int>& heights) { int n = heights.size(); vector<long long> suffix(n + 1, 0); vector<long long> prefix(n + 1, 0); stack<int> st; for (int i = 0; i < n; ++i) { while (!st.empty() && heights[st.top()] >= heights[i]) { st.pop(); } int l = st.empty() ? -1 : st.top(); // [0, i]从左到右递增的前缀高度和 = [0, l]的前缀高度和, 再加上区间(l, i]都以heights[i]为高度. prefix[i + 1] = prefix[l + 1] + 1LL * (i - l) * heights[i]; st.push(i); } st = stack<int>(); for (int i = n - 1; i >= 0; --i) { while (!st.empty() && heights[i] <= heights[st.top()]) { st.pop(); } // [i, n-1]从右到左递增的后缀高度和 = [r, n-1]的后缀高度和 int r = st.empty() ? n : st.top(); suffix[i] = suffix[r] + 1LL * (r - i) * heights[i]; st.push(i); } long long max_sum = 0; for (int i = 0; i < n; ++i) { // [0, i]的前缀以及[i, n-1]的后缀, 重复计入了一个height[i], 需要减去 long long sum = prefix[i + 1] + suffix[i] - heights[i]; max_sum = max(max_sum, sum); } return max_sum; } }; ``` 前后缀数组长度定义为 `n`： ```cpp // 思路二: // 写法二: 前后缀数组长度定义为n class Solution { public: long long maximumSumOfHeights(vector<int>& heights) { int n = heights.size(); vector<long long> suffix(n, 0); vector<long long> prefix(n, 0); stack<int> st; for (int i = 0; i < n; ++i) { while (!st.empty() && heights[st.top()] >= heights[i]) { st.pop(); } // [0, i]从左到右递增的前缀高度和 = [0, l]的前缀高度和, 再加上区间(l, i]都以heights[i]为高度. if (st.empty()) { prefix[i] = 1LL * (i + 1) * heights[i]; } else { int l = st.top(); prefix[i] = prefix[l] + 1LL * (i - l) * heights[i]; } st.push(i); } st = stack<int>(); for (int i = n - 1; i >= 0; --i) { while (!st.empty() && heights[i] <= heights[st.top()]) { st.pop(); } // [i, n-1]从右到左递增的后缀高度和 = [r, n-1]的后缀高度和 if (st.empty()) { suffix[i] = 1LL * (n - i) * heights[i]; } else { int r = st.top(); suffix[i] = suffix[r] + 1LL * (r - i) * heights[i]; } st.push(i); } long long max_sum = 0; for (int i = 0; i < n; ++i) { // [0, i]的前缀以及[i, n-1]的后缀, 重复计入了一个height[i], 需要减去 max_sum = max(max_sum, prefix[i] + suffix[i] - heights[i]); } return max_sum; } }; ``` # 二维前缀和矩阵适用场景：矩阵中 **==矩形区域求和==** ### 构建前缀和矩阵 ![[Excalidraw-Solution/前缀和与差分数组_0.excalidraw.svg|500]] %%[[Excalidraw-Solution/前缀和与差分数组_0.excalidraw.md|🖋 Edit in Excalidraw]]%% ![[_attachment/00-数据结构与算法笔记/专题总结/前缀和与差分数组.assets/IMG-前缀和与差分数组-C5586C7A24C38736BB3CB3089AE8906B.png|425]] 定义 `prefix_sum[i+1][j+1]` **表示以 `[0, 0]` 为左上角、`[i, j]` 为右下角的矩阵的区域和**。 ### 计算区间和给定区间**左上角座标 `(r1, c1)`**、**右下角坐标 `(r2, c2)`**，计算**区域和**。 ![[Excalidraw-Solution/前缀和与差分数组_3.excalidraw.svg|745]] %% [[Excalidraw-Solution/前缀和与差分数组_3.excalidraw.md|🖋 Edit in Excalidraw]] %% ### 实现 ```cpp class PrefixSumMatrix { public: // 构造函数，计算二维前缀和矩阵 PrefixSumMatrix(const std::vector<std::vector<int>>& matrix) { if (matrix.empty() || matrix[0].empty()) return; int m = matrix.size(), n = matrix[0].size(); prefix_sum.assign(m + 1, std::vector<int>(n + 1, 0)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { prefix_sum[i + 1][j + 1] = matrix[i][j] + prefix_sum[i][j+1] + prefix_sum[i+1][j] - prefix_sum[i][j]; } } } // 计算区域[(r1, c1), (r2, c2)]的和，区域由左上角(r1, c1)和右下角(r2, c2)的坐标指定 int regionSum(int r1, int c1, int r2, int c2) const { return prefix_sum[r2+1][c2+1] - prefix_sum[r2+1][c1] - prefix_sum[r1][c2+1] + prefix_sum[r1][c1]; } private: std::vector<std::vector<int>> prefix_sum; }; ``` # 差分数组「**前缀和数组**」、「**原数组**」、「**差分数组**」具有下列关系： ![[_attachment/00-数据结构与算法笔记/专题总结/前缀和与差分数组.assets/IMG-前缀和与差分数组-B9FF205BFC9DF4B2AA6E65A05FB5CA17.png|450]] 适用场景：**需要频繁处理大量区间更新操作的场景** **对数组==某区间内所有元素==进行同一加减操作时，可将时间复杂度从 $O(n)$ 降为 $O(1)$，通过维护差分数组来累积多次的差量，最后一次遍历完成对区间内所有元素的更新，得到最终修改后的数组。** ## 定义 ![[_attachment/00-数据结构与算法笔记/专题总结/前缀和与差分数组.assets/IMG-前缀和与差分数组-27965E14FC44359D696284CBD8606BD0.png|575]] ## 构建差分数组 ![[Excalidraw-Solution/前缀和与差分数组_4.excalidraw.svg|433]] %%[[Excalidraw-Solution/前缀和与差分数组_4.excalidraw.md|🖋 Edit in Excalidraw]]%% ## 差分数组相关操作主要操作包括三种： - 对**原数组指定区间 `[l,r]` 中所有元素进行增减操作** - **重构原数组** - 查询原数组中位置 `i` 的元素 #### 指定区间的批量增减操作对**原数组指定区间 `[l,r]` 中所有元素进行批量增减操作： - **全部增加 `k`**：等价于对差分数组 `diff[l] += k;` 、`diff[r+1] -= k`； - **全部减少 `k`**：等价于对差分数组 `diff[l] -= k;` 、`diff[r+1] += k;` > [!caution] 使用差分数组来**==累计对 "原数组" 的增量==**时，**差分数组是对 "==增量值==" 的差分**，而不是对原数组的差分。 ![[Excalidraw-Solution/前缀和与差分数组_5.excalidraw.svg|419]] %%[[Excalidraw-Solution/前缀和与差分数组_5.excalidraw.md|🖋 Edit in Excalidraw]]%% ![[Excalidraw-Solution/前缀和与差分数组_6.excalidraw.svg|507]] %%[[Excalidraw-Solution/前缀和与差分数组_6.excalidraw.md|🖋 Edit in Excalidraw]]%% #### 重构原数组 ![[Excalidraw-Solution/前缀和与差分数组_7.excalidraw.svg|410]] %%[[Excalidraw-Solution/前缀和与差分数组_7.excalidraw.md|🖋 Edit in Excalidraw]]%% ## 差分数组实现 ```cpp class DiffArray { private: std::vector<int> diff; public: // 构建差分数组 DiffArray(std::vector<int>& array) { if (array.empty()) return; int n = array.size(); diff.resize(n); diff[0] = array[0]; for (int i = 1; i < n; ++i) { diff[i] = array[i] - array[i-1]; } } // 查询原数组中位置i的元素值 int Query(int i) { if (i >= diff.size()) throw std::runtime_error("Out of Bounds"); int x = 0; for (int j = 0; j <= i; ++j) { x += diff[j]; } return x; } // 对原数组中区间[l, r]内的元素进行增量操作 void Increment(int l, int r, int val) { diff[l] += val; // 在diff[l]增加val if (r + 1 < diff.size()) { // 在diff[r+1]减少val diff[r + 1] -= val; } } // 重构原数组 std::vector<int> Recover() { std::vector<int> origin(diff.size(), 0); origin[0] = diff[0]; for (int i = 1; i < diff.size(); ++i) { origin[i] = origin[i-1] + diff[i]; } return origin; } }; ``` ## 典型应用 1. **给定==差分数组==，通过求==前缀和==来==复原==原数组的值** 2. 利用差分数组来**累计区间增量**，得到 "**增量值的差分**"，再对该**差分数组求前缀和**，得到**各个位置的总增量**。 3. 利用差分数组**判断区间覆盖情况**，求解 "**最大重叠区间数量**"。 # 参考资料 # Footnotes