算法复盘——前缀和

一、思路前缀和预处理数组快速计算区间和O(n)预处理→O(1)查询。二、例题一维前缀和1.区域和检索 - 数组不可变303. 区域和检索 - 数组不可变 - 力扣LeetCode代码实现class NumArray { private: vector int pre_sum; public: NumArray(vectorint nums) { int n nums.size(); pre_sum.resize(n1, 0); for(int i 0; i n; i) pre_sum[i1] pre_sum[i] nums[i]; } int sumRange(int left, int right) { return pre_sum[right 1] -pre_sum[left]; } };2.最大子段和P1115 最大子段和 - 洛谷​代码实现#include bits/stdc.h using namespace std; const int N 2e5 10; int a[N], n, premin, ret; int main() { cin n; for(int i 1; i n; i) { int x; cin x; a[i] a[i-1] x; } int ret 0xc0c0c0c0; for(int i 1; i n; i) { ret max(ret, a[i] - premin); premin min(premin, a[i]); } cout ret endl; return 0; }3.和为 K 的子数组560. 和为 K 的子数组 - 力扣LeetCode思路先计算前缀和数组然后在遍历过程中维护前面出现过的最小前缀和。对于每个位置用当前前缀和减去最小前缀和就能得到以当前位置结尾的最大子数组和。代码实现class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int mp; mp[0] 1; // 前缀和为0的情况出现1次对应pre_sum[0] int pre_sum 0, cnt 0; for(int num : nums) { pre_sum num; // 查找之前有多少个前缀和等于 pre_sum - k if(mp.contains(pre_sum - k) ) cnt mp[pre_sum - k]; mp[pre_sum]; } return cnt; } };二位前缀和1.激光炸弹P2280 [HNOI2003] 激光炸弹 - 洛谷问题分析地图坐标范围0 ≤ x,y ≤ 5000同一位置可能有多个目标价值要累加炸弹是R×R 正方形目标必须在正方形内部才被摧毁目标找一个 R×R 正方形使内部总价值最大思路先把所有点的价值累加进矩阵再算前缀和。然后枚举每个 R×R 正方形的右下角用前缀和公式 O (1) 算和最后取最大。代码实现#include bits/stdc.h using namespace std; typedef long long LL; const int N 5010; int n, m; LL a[N][N], st[N][N]; int main() { cin n m; while(n--) { int x, y, v; cin x y v; a[x][y] v; } n 5001; // 前缀和数组 for(int i 1; i n; i) { for(int j 1; j n; j) { st[i][j] st[i-1][j] st[i][j-1] - st[i-1][j-1] a[i][j]; } } // 枚举炸弹的位置 LL ret 0; m min(m, n); for (int x2 m; x2 n; x2) { for (int y2 m; y2 n; y2) { int x1 x2 - m 1, y1 y2 - m 1; LL tmp st[x2][y2] - st[x1-1][y2] - st[x2][y1-1] st[x1-1][y1-1]; ret max(ret, tmp); } } cout ret endl; return 0; }