从零学会基础算法前缀和差分：数组区间求和离散化基础

首先祝大家劳动节快乐开学两个月来学的东西不多主要掌握了两块内容前缀和/差分/离散化 和 数学基础。本文是第一篇重点整理前缀和相关内容。编程语言C 排版助手AI一、数组的三个简化技巧1. 前缀和核心思想在输入数组时用另一个数组预先存储前缀和从而快速计算任意区间的总和。公式构建prefix[i] prefix[i-1] a[i]查询区间 [l, r] 的和ans prefix[r] - prefix[l-1]题目区间求和给定一个长度为 n 的数组 a[1..n]有 q 次查询每次查询给出 l, r要求计算 a[l] a[l1] ... a[r] 的和。#includestdio.h int n; int a[100005]; long long prefix[100005]; int q; int main() { scanf(%d %d, n, q); int i; for(i 1; i n; i){ scanf(%d, a[i]); prefix[i] prefix[i-1] (long long)a[i]; } for(i 0; i q; i){ int l, r; scanf(%d %d, l, r); long long ans prefix[r] - prefix[l-1]; printf(%lld\n, ans); } return 0; }进阶二维前缀和核心思想思路与一维相同只是扩展到二维平面。公式构建prefix[i][j] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1] a[i][j]查询矩形 (x1,y1) 到 (x2,y2) 的和 ans prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] prefix[x1-1][y1-1]题目子矩阵求和给定一个 n × m 的矩阵有 q 次查询每次查询给出一个矩形区域的左上角 (x1, y1) 和右下角 (x2, y2)要求计算该矩形区域内所有元素的和。#includestdio.h int n,m,q; int a[1005][1005]; long long prefix[1005][1005]; int main() { scanf(%d %d %d,n,m,q); int i,j; for(i1;in;i){ for(j1;jm;j){ scanf(%d,a[i][j]); prefix[i][j]prefix[i-1][j]prefix[i][j-1]-prefix[i-1][j-1]a[i][j]; } } for(i0;iq;i){ int x1,y1,x2,y2; scanf(%d %d %d %d,x1,y1,x2,y2); long long ansprefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]prefix[x1-1][y1-1]; printf(%lld\n,ans); } return 0; }2.差分给定一个长度为 n 的数组初始值已知。 接下来进行 q 次操作每次操作给出三个整数 l, r, x表示将数组中第 l 个到第 r 个元素包含两端的值都增加 x。 请输出经过所有操作后数组中每个元素的最终值。要点在多次对区间内连续的一段进行加减操作时可以利用差分一维差分的定义是相邻元素的差值我们需要知道一个结论是差分的前缀和是原数组而差分的变化量的前缀和是原数组的变化量如对[l,r]区间内的元素加x,用diff表示元素的变化量则diff[l],diff[r1]--;处理完之后对diff求前缀和就是当前元素增加的值。#includestdio.h int n,q; int a[100005]; int diff[1000005]; int main() { scanf(%d %d,n,q); int i; for(i1;in;i){ scanf(%d,a[i]); } for(i0;iq;i){ int l,r,x; scanf(%d %d %d,l,r,x); diff[l]x;diff[r1]-x; } long long currentadd0; for(i1;in;i){ currentadddiff[i]; a[i]currentadd; } for(i1;in;i){ printf(%d ,a[i]); } return 0; }进阶二维差分题目有一个 N×M 的房间初始时每个格子都是空的。现在有 Q 次操作每次操作给出一个矩形区域的左上角 (x1, y1) 和右下角 (x2, y2)表示在这个区域内铺上一层地毯。问Q 次操作后每个格子上有多少层地毯要点通过一维前缀和和差分的关系我们其实就能发现差分和前缀和是互逆的即差分的前缀和是原数组前缀和的差分是原数组而二维差分的定义是通过二维前缀和的公式逆向推到的diff[i][j]a[i][j]-a[i][j-1]-a[i-1][j]a[i-1][j-1];则对一个矩形区域内只有四个点的差分发生了变化同理#includestdio.h int diff[1005][1005]; int main() { int n, m, q; scanf(%d %d %d, n, m, q); int i; for(i 0; i q; i){ int x1, y1, x2, y2; scanf(%d %d %d %d, x1, y1, x2, y2); // 二维差分标记 diff[x1][y1]; diff[x1][y21]--; diff[x21][y1]--; diff[x21][y21]; } // 求二维前缀和原地还原 int j; for(i 1; i n; i){ for(j 1; j m; j){ diff[i][j] diff[i-1][j] diff[i][j-1] - diff[i-1][j-1]; printf(%d , diff[i][j]); } printf(\n); } return 0; }3.离散化当数轴范围覆盖非常大而开不了这么大的空间时但个数却远远小于范围可以通过离散化来遍历题目区间覆盖计数有 n 个区间 [l₁, r₁], [l₂, r₂], ..., [lₙ, rₙ]坐标范围可能很大比如 -10⁹ 到 10⁹但区间数量 n ≤ 10⁵。要求找出被最多区间覆盖的点输出最大覆盖次数。输入格式第一行一个整数 n接下来 n 行每行两个整数 lᵢ, rᵢ输出格式一个整数表示最大覆盖次数要点离散化的顺序可以归纳为三步1.接收关键点2.排序关键点并去重去重函数可以这样写int unique(int len){ int i; int j0; for(i0;ilen;i){ if(i0||coords[i]!coords[i-1]){ coords[j]coords[i]; } } return j; }3.二分查找映射然后差分#includestdio.h #includestdlib.h int n; int l[100005],r[100005]; int coords[200005]; int diff[200005]; int cmp(const void*a,const void*b){ return *(int *)a-*(int *)b; } int unique(int len){ int i; int j0; for(i0;ilen;i){ if(i0||coords[i]!coords[i-1]){ coords[j]coords[i]; } } return j; } int lower_bound(int target,int len){ int left0,rightlen-1; while(leftright){ int mid(right-left)/2left; if(coords[mid]target)leftmid1; else rightmid-1; return left; } } int main() { scanf(%d,n); int i; int coordslen0; for(i0;in;i){ scanf(%d %d,l[i],r[i]); coords[coordslen]l[i]; coords[coordslen]r[i]; } qsort(coords,coordslen,sizeof(int),cmp); coordslenunique(coordslen); for(i0;in;i){ int idx1lower_bound(l[i],coordslen); int idx2lower_bound(r[i],coordslen); diff[idx1];diff[idx21]--; } int currentadd0; int max0; for(i0;icoordslen1;i){ currentadddiff[i]; if(maxcurrentadd)maxcurrentadd; } printf(%d,max); return 0; }进阶二维离散化给定一个巨大的网格平面上面有 X 个矩形。求这些矩形覆盖的总面积重叠部分只算一次。1 ≤ N, M ≤ 10^91 ≤ X ≤ 1000步骤与一维同理不多赘述#includestdio.h #includestdlib.h int n; int x[10005]; int y[10005]; int x1[10005],y1[10005],x2[10005],y2[10005]; int xcnt0,ycnt0; int diff[2005][2005]; int cmp(const void*a,const void*b){ return *(int *)a-*(int *)b; } int unique(int len,int *arr){ int i; int j0; for(i0;ilen;i){ if(i0||arr[i]!arr[i-1]){ arr[j]arr[i]; } } return j; } int find_idx(int target,int len,int*arr){ int left0,rightlen-1; while(leftright){ int mid(right-left)/2left; if(arr[mid]target)leftmid1; else rightmid-1; } return left; } int main() { scanf(%d,n); int i,j; for(i0;in;i){ scanf(%d %d %d %d,x1[i],y1[i],x2[i],y2[i]); x[xcnt]x1[i]; x[xcnt]x2[i]1; y[ycnt]y1[i]; y[ycnt]y2[i]1; } qsort(x,xcnt,sizeof(int),cmp); qsort(y,ycnt,sizeof(int),cmp); xcntunique(xcnt,x); ycntunique(ycnt,y); for(i0;in;i){ int findx1find_idx(x1[i],xcnt,x); int findx2find_idx(x2[i]1,xcnt,x); int findy1find_idx(y1[i],ycnt,y); int findy2find_idx(y2[i]1,ycnt,y); diff[findx1][findy1]; diff[findx2][findy1]--; diff[findx1][findy2]--; diff[findx2][findy2]; } long long count0; for(i0;ixcnt;i){ for(j0;jycnt;j){ if(i0) diff[i][j]diff[i-1][j]; if(j0) diff[i][j]diff[i][j-1]; if(i0j0) diff[i][j]-diff[i-1][j-1]; if(diff[i][j]0) count (long long)(x[i1]-x[i])*(y[j1]-y[j]); } } printf(%lld,count); return 0; }不足之处可以补充