## 【前缀和与差分】题单 ### 一、公式 #### 前缀和公式 一维：$s[i] = a[i] + s[i-1]$ 二维：$s[i][j] = a[i][j] + s[i-1] [j] + s[ i] [j-1] - s[i-1][j-1]$ #### 差分公式 一维：$b[i] =s[i] - s[i-1]$ 二维：$b[i] = s[i][j] - s[i-1][j]-s[i][j-1]+s[i-1][j-1]$ ### 二、题单 #### [$P1115$ 最大子段和](https://www.luogu.com.cn/problem/P1115) **分析** 先求每个位置的前缀和，然后去找 **该位置前面** 前缀和的最小值，如果要求一段和最大，就要用这段和 **减去前面最小的值**。 ##### 一维前缀和解法 ```cpp {.line-numbers} #include using namespace std; const int N = 200100; int n, a[N], s[N], ans[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i]; // 前缀和 int mi = 0; for (int i = 1; i <= n; i++) { ans[i] = s[i] - mi; mi = min(mi, s[i]); } int res = INT_MIN; for (int i = 1; i <= n; i++) res = max(res, ans[i]); cout << res << endl; return 0; } ``` ##### $DP$ 解法 **状态定义** $dp[i]$: 走完前$i$个数字，在此阶段中可以获取到的最大子段和。 **状态转移** - 如果从前面的结果中借力划算，那就借力 - 如果借力不合适，那就自己单干 ```cpp {.line-numbers} #include using namespace std; const int N = 200100; int ans = INT_MIN; int n; int a[N], dp[N]; // dp[i]定义：前i个范围内，区间和的最大值 int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = max(dp[i - 1] + a[i], a[i]); ans = max(ans, dp[i]); } printf("%d\n", ans); return 0; } ``` #### [$P1083$ [$NOIP2012$ 提高组] 借教室](https://www.luogu.com.cn/problem/P1083) #### 暴力 还是先看暴力怎么做吧，对于$m$次借教室，我们可以每次把区间$s\sim t$的空教室数$r-=d$，当有一次$r<0$时，则当前这个人无法被满足，直接输出$-1$和当前这个人的号数，然后直接结束程序。如果$m$次借教室都操作完成后依然没有房间数$r<0$，则说明所有人都可以被满足，则输出$0$。 综合上述做法，得分$60$。 ```cpp {.line-numbers} #include using namespace std; int n, m; const int N = 1000010; int r[N]; int main() { cin >> n >> m; // 每一天可租借教室数 for (int i = 1; i <= n; i++) cin >> r[i]; // 从哪天到哪天，借多少个 for (int i = 1; i <= m; i++) { int d, s, t; cin >> d >> s >> t; // 从开始天到结束天 for (int j = s; j <= t; j++) { r[j] -= d; // 减去借走的教室数 if (r[j] < 0) { // 小于0了！ cout << -1 << endl << i << endl; return 0; } } } cout << 0 << endl; return 0; } ``` 显然，这样做法的时间复杂度时$O(N*M)$的，无法通过此题，从而我们可以推知该题正确的时间复杂度应该是$log$级的。 #### 正解 既然时间复杂度时$log$级的，于是想到了二分。 再看到每个人借教室的时间可以看成一个区间，且该区间只会对其他在该区间要借教室的人产生影响，对于区间之外的借教室的人是不会产生影响的，于是又想到了差分。 **差分序列**：（可用于区间增减）记录相邻两个量的变化量，所以当在一段区间$[l,r]$上增加$d$时，只需要在$l$处加$d$，在$r+1$处$-d$ 即可。 对于为什么可以二分：如果一个订单无法被满足，则它后面的订单全都不能被满足；如果一个订单可以被满足，则它前面的订单都可以被满足,这恰恰吻合了我们二分的性质。 ```cpp {.line-numbers} #include using namespace std; const int N = 1000010; #define int long long #define endl "\n" int n, m; // 天数和订单的数量 int r[N]; // 第i天学校有r[i]个教室可借用 int d[N], s[N], t[N]; // 借的教室数目、从第s天借到t天 int b[N]; // 差分数组 bool check(int mid) { // 判断能不能通过前mid个订单 memset(b, 0, sizeof b); // 每次判断都要先初始化差分数组 int sum = 0; // 记录需要借的教室数 // ① 构建差分数组 for (int i = 1; i <= mid; i++) { // 枚举范围内[1~mid]所有订单 b[s[i]] += d[i]; // 第i个订单，因为只会对在s~l之间要借用教室的人产生影响，所以可以差分 b[t[i] + 1] -= d[i]; // 差分,注意:是t[i]+1，因为要包含t[i]这个点 } // ② 还原成原数组,sum=a[i],也就是第i天需要借的教室总数 for (int i = 1; i <= n; i++) { // 枚举每一天 sum += b[i]; // 因为b是差分数组，所以sum就是在第i天的借教室的总数 if (sum > r[i]) return false; // 如果要借的教室多于空的教室,返回不可行 } return true; // 返回可行 } signed main() { cin >> n >> m; // n:天数，m：订单数量 for (int i = 1; i <= n; i++) cin >> r[i]; // 第i天可以租借的教室数量 for (int i = 1; i <= m; i++) cin >> d[i] >> s[i] >> t[i]; // 借多少个，从哪天借到哪天 /* ① 整体检查，如果所有订单都能通过，则输出0 先定性，再定量！ 我们先不思考二分不二分，先用check函数获取所有订单是不是可以通过，如果能通过，那二分个啥！ 如果不能过，再已知有问题订单的情况下，再去找出问题订单，这样思路是最清晰的！ 避免不管是否有问题订单，全都冗杂到一个二分检查办法中去，那样容易思路不清，造成丢分！ */ if (check(m)) { // 如果全部满足 cout << 0 << endl; // 输出0 exit(0); // 直接结束程序 } /* ② 整体检查未通过，知道肯定有订单无法满足，此时，再想办法找出是哪个订单第一个出现不满足的情况 难道要一个个订单检查吗？ 不断的增加订单，会使得差分数组变化，但我们只看差分数组是不能判断是否有问题发生的，需要把差分数组还原 为原数组后，才能进行检查,每输入一个订单，就还原一下原数组，那样就太慢了。 能不能少还原，还能判断准呢？ 答：可以的，因为这件事具有单调性！第x个订单加上后: (1)如果1~x都符合条件，那证明前面的x-1个订单都是OK的， (2)如果1~x不符合条件，那后续的追加更多订单后的检查也肯定会失败！ 所以，可以使用二分进行求解查找是哪个订单导致第一个失败情况出现。 */ int l = 1, r = m; // 二分左右区间 while (l < r) { int mid = l + r >> 1; if (check(mid)) // 如果可行 l = mid + 1; // 增多订单 else // 否则 r = mid; // 减少订单 } if (l == r) cout << 0 << end; ; cout << "-1" << endl << l; // 输出-1和 第一个不符合条件的订单 } ``` #### [$P3406$ 海底高铁](https://www.luogu.com.cn/problem/P3406) **题意** 每一个条铁路都会被经过多次，求这一条铁路是办卡+充值花的钱少,还是直接买多次票花的钱少。 **分析** 我们其实只需要知道一条铁路被访问了几次就可以了，再通过比较 $c+b*n$ 和 $a$ 的值，就可以知道是买票好还是买卡好了。 一个点到另外一个点的路径中，中间经过的铁路都会被访问一遍，如果每次都一个一个的加这样太慢了,会$TLE$ 发现这些铁路实质上是一维的，并且是关于区间的修改的,那么就可以用差分优化了 ```cpp {.line-numbers} #include using namespace std; const int N = 100005; #define int long long // 数据范围是10^5*10^5,所以注意要开ll #define endl "\n" int p[N]; // 要访问的城市顺序 int x[N], y[N], z[N]; // 买票,充值,买卡 int b[N]; // 差分数组 int res; // 结果 int n, m; // 共n个城市，要去m个城市 signed main() { cin >> n >> m; // 共n个城市，要去m个城市 for (int i = 0; i < m; i++) cin >> p[i]; // 访问顺序,下标都是从0开始的 for (int i = 1; i < n; i++) cin >> x[i] >> y[i] >> z[i]; // 每个城市的买票、充值、买卡价格，此处下标从1开始，是因为P0不需要再到P0 for (int i = 1; i < m; i++) { // 0号点是出发点，没有意义，不讨论，从1号开始，最大是 m-1 int s = p[i - 1], t = p[i]; // 起点, 终点 if (s > t) swap(s, t); // 我KAO，原来题意是说：如果你从2~5去则一定走了2,3,4,5这四个城市，铁路按线段处理，即2,3,4号线段 b[s] += 1, b[t] -= 1; // s在内，t不在内，因为是按线段处理的 } for (int i = 1; i <= n; i++) b[i] += b[i - 1]; // 差分数组变形为前缀和数组 // 判断一下 n*a[i]和n*b[i]+c[i]的大小 for (int i = 1; i < n; i++) res += min(b[i] * x[i], b[i] * y[i] + z[i]); // b[i]:走几次，x[i]*b[i]:买票需要花费多少钱；b[i] * y[i] + z[i]:办卡+冲值共需要花费多少钱 // 两个打擂台，谁少就用谁，每一块线段都花费最少，整体必须花费最少，贪心 cout << res << endl; // 输出 } ``` #### [$P5638$ 光骓者的荣耀](https://www.luogu.com.cn/problem/P5638) **题目大意** 用最少时间要将所有城市全部访问完，若有传送器可使用传送器。 **坑点** - 需要考虑传送器数量与城市的数量 ，若传送器大于城市输出$0$ - 需要考虑数据范围较大，`long long int` **数据范围** 开一个大于$10$的$6$次方的数据 **思路** ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202312181353674.png) 上图是一个$n = 6$的样例。从城市$1$到城市$6$，需要$3+2+4+5+4=18$天。 假如传送器的半径为$2$。可以逐个枚举。 - 如果在城市$1$使用传送器，则一下子可到达城市$3$，然后城市$3$到城市$6$，需要$13$天。这种情况下从城市$1$到城市$6$，需要$13$天。 - 如果在城市$2$使用传送器，则从城市$1$先用$3$天的时间到达城市$2$，再用传送器到达城市$4$，从城市$4$到城市$6$需要$9$天。这种情况下从城市$1$到城市$6$，共需要$3 + 9 = 12$天。 - 如果在城市$3$使用传送器，则从城市$1$到城市$3$需要$5$天，从城市$3$使用传送器一下子到达城市$5$，从城市$5$到城市$6$需要$4$天。这种情况下从城市$1$到城市$6$，共需要$5+4=9$天。 - 如果在城市$4$使用传送器，则从城市$1$到城市$4$需要$9$天，从城市$4$使用传送器一下子到达城市$6$。这种情况下从城市$1$到城市$6$，共需要$9$天。 - 如果在城市$5$使用传送器，则从城市$1$到城市$5$需要$14$天，从城市$5$使用传送器一下子到达城市$6$。这种情况下从城市$1$到城市$6$，共需要$14$天。 所以在城市$3$或城市$4$使用传送器，可以使得总共花费的时间最少。 **$Code$** ```cpp {.line-numbers} #include using namespace std; #define int long long #define endl "\n" const int N = 1000010; int n, k; int a[N], s[N]; int ans = LONG_LONG_MAX; // 预求最小先设最大 signed main() { cin >> n >> k; for (int i = 2; i <= n; i++) { // i代表第i个城市 cin >> a[i]; // a[i]代表第i-1个城市到第i个城市需要的时间 s[i] = s[i - 1] + a[i]; // 利用前缀存储从第1个城市到第i+1个城市的累积时间 } // 感悟：代码越多，可读性越强 for (int i = 1; i <= n; i++) { // 遍历每个城市 int far = i + k; // 传送到最远的点 if (far >= n) far = n; // 最远不能超过n点 int time = s[i] + s[n] - s[far]; // s[n]-s[far]= 剩余道路需要走的时间,s[i]:前面道路需要走的时间 ans = min(ans, time); // 取最小值 } cout << ans << endl; // 输出 } ``` #### [$P1719$ 最大加权矩阵](https://www.luogu.com.cn/problem/P1719) **$O(N^4)$算法** ```cpp {.line-numbers} #include using namespace std; const int N = 130; int n; int a[N][N]; // 存储题目中的矩阵 int s[N][N]; // 二维前缀和 int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; } } int mx = INT_MIN; // 存储答案 // 遍历左上角坐标，与，右下角坐标 for (int x1 = 1; x1 <= n; x1++) { for (int y1 = 1; y1 <= n; y1++) { for (int x2 = 1; x2 <= n; x2++) for (int y2 = 1; y2 <= n; y2++) { if (x2 < x1 || y2 < y1) continue; // 如果左上角比右下角还要大，就不用求了，下一个 mx = max(mx, s[x2][y2] + s[x1 - 1][y1 - 1] - s[x2][y1 - 1] - s[x1 - 1][y2]); // 求最大值 } } } cout << mx << endl; // 输出 return 0; } ``` **$O(N^3)$算法**【选读】 > **引子** 给出一段序列，选出其中连续且非空的一段使得这段和最大。 第一行是一个正整数$N$，表示了序列的长度。($N<=200000$) 这是 $P1115$ 最大子段和 的描述，也就是本题的一维版本。 > $DP$方程：`dp[i]=max(dp[i-1]+a[i],a[i])` $a[i]$表示这个数列的第$i$项。 那么我们如何来处理这一题呢？ 我们可以考虑将矩形压缩成一维，比如处理一个$2$行的矩形时，将$a [i][j]$与$a[i-1][j]$相加，成为一个新的数组$f[n]$，再使用上述代码进行动态规划，找出局部最优解。 那如何来快速将矩形折叠呢？ 我们可以选择 **前缀和** 简单来说，就是在输入的时候，再次加上$a[i-1][j]$，这样可以用减法来快速表示压缩的矩形。 具体代码如下： ```cpp {.line-numbers} cin >> n; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ cin >> a[i][j]; a[i][j]+=a[i-1][j];//根据前缀和定义处理 } ``` 用样例来表示，输入的是： ```cpp {.line-numbers} 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 ``` 在经过前缀和处理之后，输出的是这个： ```cpp {.line-numbers} 0 -2 -7 0 9 0 -13 2 5 1 -17 3 4 9 -17 1 ``` 可以模拟一下，$a[i][j] - a[i-k][j]$正好是以$i$为最下面一行，往上$k$行的压缩结果，这就很方便地表示了压缩后的矩形。 **那又怎么循环找出各行为最下一行，不同行数的矩阵最大值呢？** 我用$i$表示以$i$为最下一行，$k$表示向上$k$行，代码如下: ```cpp {.line-numbers} for(i=1;i<=n;i++){ for(k=1;k<=i;k++){ } } ``` $k<=i$，保证了$i-k>=0$。 那再次循环，运用第一个代码的简单变形，可以求出以$i$为最下一行，向上$k$行的矩形最大值，多次更新$ans$，愉快$AC$。 **$Code$** ```cpp {.line-numbers} #include using namespace std; const int N = 150; int a[N][N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin >> a[i][j]; a[i][j] += a[i - 1][j]; // 按列计算前缀和 } int ans = INT_MIN; // 预求最大，先设最小 for (int i = 1; i <= n; i++) // 最底下一行 for (int k = 1; k <= i; k++) { // 往上k行 int dp[N] = {0}; // dp[j]表示压缩的矩形前j列的最大累加值 for (int j = 1; j <= n; j++) { // 第j列 int s = a[i][j] - a[i - k][j]; // 求压缩的矩形第j列的值 dp[j] = max(dp[j - 1] + s, s); // 动态规划,到j列为止，最大的连续累加和 ans = max(ans, dp[j]); // 更新答案 } } cout << ans << endl; // 愉快AC return 0; } ``` #### [$P2004$ 领地选择](https://www.luogu.com.cn/problem/P2004) 二维前缀和祼题，不解释。 ```cpp {.line-numbers} #include using namespace std; const int N = 1010; int n, m, c; int a[N][N], s[N][N]; int mx = INT_MIN; int main() { cin >> n >> m >> c; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> a[i][j]; s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; // 构建二维前缀和 } int x, y; for (int i = c; i <= n; i++) // 边长为c for (int j = c; j <= m; j++) { if (s[i][j] - s[i - c][j] - s[i][j - c] + s[i - c][j - c] > mx) { mx = s[i][j] + s[i - c][j - c] - s[i - c][j] - s[i][j - c]; x = i - c + 1; y = j - c + 1; } } printf("%d %d", x, y); return 0; } ``` #### [$P3397$ 地毯](https://www.luogu.com.cn/problem/P3397) **分析** 看到这里的时候，我就想到了一个矩阵的某个子矩阵进行加减，瞬间想到二维差分和二位前缀和,二位差分的公式为： ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202312170848375.png) 由差分算的二位前缀和公式： ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202312170849629.png) ```cpp {.line-numbers} #include using namespace std; const int N = 1010; int b[N][N], s[N][N]; int n, m; int main() { cin >> n >> m; while (m--) { // 从0开始构建差分数组 int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; b[x1][y1] += 1; // 进行子矩阵的加减，差分 b[x2 + 1][y1] -= 1; b[x1][y2 + 1] -= 1; b[x2 + 1][y2 + 1] += 1; } // 还原为原始数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { s[i][j] = b[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; // 把之前的加减结果进行求和 printf("%d ", s[i][j]); // 注意输出格式，每个数带一个空格 } printf("\n"); // 结束一行的输出输出一个换行符号 } return 0; } ```