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

首先祝大家劳动节快乐！开学两个月来学的东西不多，主要掌握了两块内容：前缀和/差分/离散化 和 数学基础。本文是第一篇，重点整理前缀和相关内容。
编程语言：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[l+1] + ... + a[r] 的和。

#include<stdio.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)，要求计算该矩形区域内所有元素的和。

#include<stdio.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(i=1;i<=n;i++){ for(j=1;j<=m;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(i=0;i<q;i++){ int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); long long ans=prefix[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[r+1]--;

处理完之后对diff求前缀和就是当前元素增加的值。

#include<stdio.h> int n,q; int a[100005]; int diff[1000005]; int main() { scanf("%d %d",&n,&q); int i; for(i=1;i<=n;i++){ scanf("%d",&a[i]); } for(i=0;i<q;i++){ int l,r,x; scanf("%d %d %d",&l,&r,&x); diff[l]+=x;diff[r+1]-=x; } long long currentadd=0; for(i=1;i<=n;i++){ currentadd+=diff[i]; a[i]+=currentadd; } for(i=1;i<=n;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];

则对一个矩形区域内只有四个点的差分发生了变化，同理

#include<stdio.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][y2+1]--; diff[x2+1][y1]--; diff[x2+1][y2+1]++; } // 求二维前缀和，原地还原 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 j=0; for(i=0;i<len;i++){ if(i==0||coords[i]!=coords[i-1]){ coords[j++]=coords[i]; } } return j; }

3.二分查找映射然后差分

#include<stdio.h> #include<stdlib.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 j=0; for(i=0;i<len;i++){ if(i==0||coords[i]!=coords[i-1]){ coords[j++]=coords[i]; } } return j; } int lower_bound(int target,int len){ int left=0,right=len-1; while(left<=right){ int mid=(right-left)/2+left; if(coords[mid]<target)left=mid+1; else right=mid-1; return left; } } int main() { scanf("%d",&n); int i; int coordslen=0; for(i=0;i<n;i++){ scanf("%d %d",&l[i],&r[i]); coords[coordslen++]=l[i]; coords[coordslen++]=r[i]; } qsort(coords,coordslen,sizeof(int),cmp); coordslen=unique(coordslen); for(i=0;i<n;i++){ int idx1=lower_bound(l[i],coordslen); int idx2=lower_bound(r[i],coordslen); diff[idx1]++;diff[idx2+1]--; } int currentadd=0; int max=0; for(i=0;i<coordslen+1;i++){ currentadd+=diff[i]; if(max<currentadd)max=currentadd; } printf("%d",max); return 0; }

进阶：二维离散化

给定一个巨大的网格平面，上面有 X 个矩形。求这些矩形覆盖的总面积（重叠部分只算一次）。

1 ≤ N, M ≤ 10^9
1 ≤ X ≤ 1000

步骤与一维同理，不多赘述；

#include<stdio.h> #include<stdlib.h> int n; int x[10005]; int y[10005]; int x1[10005],y1[10005],x2[10005],y2[10005]; int xcnt=0,ycnt=0; 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 j=0; for(i=0;i<len;i++){ if(i==0||arr[i]!=arr[i-1]){ arr[j++]=arr[i]; } } return j; } int find_idx(int target,int len,int*arr){ int left=0,right=len-1; while(left<=right){ int mid=(right-left)/2+left; if(arr[mid]<target)left=mid+1; else right=mid-1; } return left; } int main() { scanf("%d",&n); int i,j; for(i=0;i<n;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); xcnt=unique(xcnt,x); ycnt=unique(ycnt,y); for(i=0;i<n;i++){ int findx1=find_idx(x1[i],xcnt,x); int findx2=find_idx(x2[i]+1,xcnt,x); int findy1=find_idx(y1[i],ycnt,y); int findy2=find_idx(y2[i]+1,ycnt,y); diff[findx1][findy1]++; diff[findx2][findy1]--; diff[findx1][findy2]--; diff[findx2][findy2]++; } long long count=0; for(i=0;i<xcnt;i++){ for(j=0;j<ycnt;j++){ if(i>0) diff[i][j]+=diff[i-1][j]; if(j>0) diff[i][j]+=diff[i][j-1]; if(i>0&&j>0) diff[i][j]-=diff[i-1][j-1]; if(diff[i][j]>0) count += (long long)(x[i+1]-x[i])*(y[j+1]-y[j]); } } printf("%lld",count); return 0; }

不足之处可以补充