聊城建设路小学网站,织梦网站被黑,中小企业网络营销案例,wordpress又拍报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周#xff08;读者可以按…报名明年4月蓝桥杯软件赛的同学们如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周读者可以按自己的进度选“正常”和“快进”两种计划。 每周3次集中答疑周三、周五、周日晚上在QQ群上答疑 文章目录 1. 前缀和概念2. 前缀和例题例1 基本应用例2 基本应用例3 异或的前缀和例4 二维前缀和 3. 差分4. 差分例题例5 差分的基本应用例6 差分的基本应用 第9周: 前缀和与差分
1. 前缀和概念 前缀和是一种操作简单但是非常有效的优化方法能把计算复杂度为O(n)的区间计算优化为O(1)的端点计算。 前缀和是出题者喜欢考核的知识点在算法竞赛中很常见在蓝桥杯大赛中几乎必考。原因有两点 一是简单方便在很多场景下应用与其他考点结合 二是可以考核不同层次的能力例如一道题用暴力法能通过30%的测试用前缀和优化后能通过70%~100%的测试。 首先了解“前缀和”的概念。一个长度为n的数组a[1] ~ a[n]前缀和sum[i]等于a[1] ~ a[i]的和 sum[i] a[1] a[2] … a[i] 利用递推可以在O(n)时间内求得所有前缀和 sum[i] sum[i-1] a[i] 如果预计算出前缀和就能利用它快速计算出数组中任意一个区间a[i] ~ a[j]的和。即 a[i] a[i1] … a[j-1] a[j] sum[j] - sum[i-1] 上式说明复杂度为O(n)的区间求和计算优化到了O(1)的前缀和计算。
2. 前缀和例题 前缀和是一种很简单的优化技巧应用场合很多在竞赛中极为常见。如果建模时发现有区间求和操作可以考虑使用前缀和优化。
例1 基本应用
例题1 求和 题解这是一道非常直白的前缀和题。为了说明前缀和的作用下面用两种方法求解本题。 1通过30%的测试。直接按题意两两相乘然后求和这是暴力法。 如果用C编程需要考虑S是否能用long long类型表示。若每个ai都是最大的1000每两个相乘等于106n个数两两相乘共 n 2 / 2 20000 0 2 / 2 2 × 1 0 10 n^2/2 200000^2/2 2×10^{10} n2/22000002/22×1010次和S约为 2 × 1 0 10 × 1 0 6 2 × 1 0 16 2×10^{10}×10^6 2×10^{16} 2×1010×1062×1016。long long能表示的最大正整数远大于 2 × 1 0 16 2×10^{16} 2×1016所以不需要用高精度处理大数。
#includebits/stdc.h
using namespace std;
int main() {int n; cin n; // 读取nvectorint a(n); //用vector定义数组a[]for (int i 0; i n; i) cin a[i]; // 读取a[]int s 0;for (int i 0; i n; i) // 用两个for循环计算两两相乘然后求和for (int j i 1; j n; j)s a[i] * a[j];cout s endl;return 0;
}下面分析代码的时间和空间效率。 1时间复杂度。代码执行了多少步骤花了多少时间 代码第8、9行有2层for循环循环次数是 n − 1 n − 2 . . . 1 ≈ n 2 / 2 n-1 n-2 ... 1 ≈ n^2/2 n−1n−2...1≈n2/2计算复杂度为 O ( n 2 ) O(n^2) O(n2)。 对于30%的测试数据n 1000循环次数$1000^2/2 50,000。计算时间远远小于题目的时间限制1s能够通过测试。 对于100%的测试数据n 200000循环次数$200000 2 / 2 2 × 1 0 10 2/2 2×10^{10} 2/22×1010。计算时间远大于题目的时间限制1s超时不能通过测试。 2空间复杂度也就是程序占用的内存空间。对于100%的数据若用数组int a[200000]存储数据int是32位整数占用4个字节所以int a[200000]共使用了800K空间远小于题目的空间限制256MB。 2通过100%测试。本题利用前缀和能得到100%的分数。 把计算式子变换为 S ( a 1 a 2 . . . a n − 1 ) × a n ( a 1 a 2 . . . a n − 2 ) × a n − 1 ( a 1 a 2 . . . a n − 3 ) × a n − 2 . . . ( a 1 a 2 ) × a 3 a 1 × a 2 S(a_1a_2 ...a_{n-1})×a_n(a_1a_2 ...a_{n-2})×a_{n-1}(a_1a_2...a_{n-3})×a_{n-2}...(a_1a_2)×a_3a_1×a_2 S(a1a2...an−1)×an(a1a2...an−2)×an−1(a1a2...an−3)×an−2...(a1a2)×a3a1×a2 其中括号内的部分是前缀和 s u m [ i ] a 1 a 2 … a i sum[i] a_1a_2… a_i sum[i]a1a2…ai把上式改为 S s u m [ n − 1 ] × a n s u m [ n − 2 ] × a n − 1 s u m [ n − 3 ] × a n − 2 . . . s u m [ 2 ] × a 3 s u m [ 1 ] × a 2 S sum[n-1] ×a_n sum[n-2]×a_{n-1} sum[n-3]×a_{n-2} ... sum[2]×a_3 sum[1]×a_2 Ssum[n−1]×ansum[n−2]×an−1sum[n−3]×an−2...sum[2]×a3sum[1]×a2 式子中用到的前缀和sum[1] ~ sum[n-1]用递推公式sum[i] sum[i-1] a[i]做一次for循环就能全部提前计算出来。 下面的C代码第8行先预计算出前缀和sum[]然后利用sum[]求S。
#includebits/stdc.h
using namespace std;
int main() {int n; cin n; //读nvectorint a(n1,0); //定义数组a[]并初始化为0for (int i1; in; i) cin a[i]; // 读a[1]~a[n]vectorlong long sum(n1, 0); //定义前缀和数组 sum[]并初始化为0for (int i1; in; i) sum[i]a[i]sum[i-1]; // 预计算前缀和sum[1]~sum[n-1]long long s 0; for (int i1; in; i) s sum[i]*a[i1]; // 计算和scout s endl;return 0;
}代码的计算量是多少第8、10行各有一层for循环分别计算n次也就是两个O(n)合起来仍然是O(n)的。对于100%的数据n 200000运行时间满足时间限制。 java代码
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt(); // 读nint[] a new int[n1]; // 定义数组a[]并初始化为0for (int i1; in; i) a[i] scanner.nextInt(); // 读取a[1]~a[n] long[] sum new long[n1]; // 定义前缀和数组 sum[]并初始化为0for (int i1; in; i) sum[i]a[i]sum[i-1]; // 预计算前缀和sum[1]~sum[n-1]long s 0;for (int i1; in; i) ssum[i]*a[i1]; // 计算和s System.out.println(s);}
}python代码
n int(input())
a [0][int(i) for i in input().split()] #读入a[1]~a[n]。a[0]不用
sum [0] * (n1) #定义前缀和
sum[1] 0
for i in range(1,n): sum[i] a[i]sum[i-1] #预计算前缀和sum[1]~sum[n-1]
s 0
for i in range(1,n): s sum[i]*a[i1] #计算和s
print(s)例2 基本应用
可获得的最小取值 第一步肯定是排序例如从小到大排序然后再进行两种操作。操作1在a[]的尾部选一个数操作2在a[]的头部选2个数。 容易想到一种简单方法每次在操作1和操作2中选较小的值。这是贪心法的思路。但是贪心法对吗分析之后发现贪心法是错误的例如{3, 1, 1, 1, 1, 1, 1}做k3次操作每次都按贪心法做3次操作2结果是6。但是正确答案是做3次操作1结果是5。 回头重新考虑所有可能的情况。设操作2做p次操作1做k-p次求和 ∑ i 1 2 p a i ∑ i n p − k 1 n a i \sum_{i1}^{2p}a_i\sum_{i{np-k1}}^{n}a_i ∑i12pai∑inp−k1nai 为了找最小的和需要把所有的p都试一遍。如果直接按上面的公式计算那么验证一个p的计算量是O(n)的验证所有的p1≤p≤k总计算量O(kn)超时。 容易发现公式的两个部分就是前缀和分别等于sum[2p]、sum[n]-sum[np-k]。如果提前算出前缀和sum[]那么验证一个p的时间是O(1)的验证所有p的总计算量是O(n)的。 下面是C代码。注意sum[]需要用long long类型。 代码的计算复杂度第10行sort()是O(nlogn)第13行是O(n)总复杂度为O(nlogn)。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 200010;
long long a[N],s[N]; //s[]是a[]的前缀和
int main(){int n, k; cin n k;for (int i 1; i n; i) scanf(%lld,a[i]);sort(a 1, a 1 n);for (int i 1; i n; i) s[i] s[i-1] a[i];ll ans 1e18;for (int p 1; p k; p)ans min(s[n] - s[np-k] s[2*p], ans);printf(%lld,ans);return 0;
}java代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int k scanner.nextInt();long[] a new long[n1];for (int i 1; i n; i) a[i] scanner.nextLong(); Arrays.sort(a, 1, n1);long[] s new long[n1];for (int i 1; i n; i) s[i] s[i-1] a[i]; long ans (long)1e18;for (int p 1; p k; p)ans Math.min(s[n] - s[np-k] s[2*p], ans); System.out.println(ans);}
}Python代码
n, k map(int, input().split())
b list(map(int, input().split()))
a[0] sorted(b) # a[0]不用从a[1]开始
s [0] * (n1)
for i in range(1, n1): s[i] s[i-1] a[i]
ans 10**18
for p in range(1, k1):ans min(s[n] - s[np-k] s[2*p], ans)
print(ans)例3 异或的前缀和 下面例题是前缀和在异或计算中的应用也是常见的应用场景。 异或和之和 n个数 a 1 − a n a_1-a_n a1−an的异或和等于 a 1 ⊕ a 2 ⊕ . . . ⊕ a n a_1⊕a_2⊕...⊕a_n a1⊕a2⊕...⊕an。 1通过30%的测试。 本题的简单做法是直接按题意计算所有子段的异或和然后加起来。 有多少个子段 长度为1的子段异或和有n个 a 1 、 a 2 、 . . . 、 a n a_1、a_2、...、a_n a1、a2、...、an 长度为2的子段异或和有n-1个 a 1 ⊕ a 2 、 a 2 ⊕ a 3 、 . . . a n − 1 ⊕ a n a_1⊕a_2、a_2⊕a_3、...a_{n-1}⊕a_n a1⊕a2、a2⊕a3、...an−1⊕an … 长度为n的子段异或和有1个 a 1 ⊕ a 2 ⊕ a 3 ⊕ . . . ⊕ a n − 1 ⊕ a n a_1⊕a_2⊕a_3⊕...⊕a_{n-1}⊕a_n a1⊕a2⊕a3⊕...⊕an−1⊕an 共 n 2 / 2 n^2/2 n2/2个子段。 下面代码第8、9行遍历所有的子段[L, R]第11行求[L,R]的字段和。共3重for循环计算复杂度 O ( n 3 ) O(n^3) O(n3)只能通过30%的测试。
#includebits/stdc.h
using namespace std;
int main(){int n; cin n;vectorint a(n); //用vector定义数组a[]for (int i 0; i n; i) cin a[i];long long ans0; //注意这里用long longfor(int L0;Ln;L) //遍历所有区间[L,R]for(int RL;Rn;R){int sum0;for(int iL;iR;i) sum^a[i]; //子段和ans sum; //累加所有子段和}coutans;return 0;
}2通过60%的测试。本题可以用前缀和优化。 记异或和 a 1 ⊕ a 2 ⊕ . . . ⊕ a i a_1⊕a_2⊕...⊕a_i a1⊕a2⊕...⊕ai的前缀和为 s i a 1 ⊕ a 2 ⊕ . . . ⊕ a i sia_1⊕a_2⊕...⊕a_i sia1⊕a2⊕...⊕ai 这里 s i s_i si是异或形式的前缀和。这样就把复杂度为O(n)的子段异或和计算 a 1 ⊕ a 2 ⊕ . . . ⊕ a i a_1⊕a_2⊕...⊕a_i a1⊕a2⊕...⊕ai优化到了O(1)的求 s i s_i si的计算。 以包含 a 1 a1 a1的子段为例这些子段的异或和相加等于 a 1 a 1 ⊕ a 2 . . . a 1 ⊕ . . . ⊕ a i . . . a 1 ⊕ . . . ⊕ a n s 1 s 2 . . . s i . . . s n a_1a_1⊕a_2...a_1⊕...⊕a_i...a_1⊕...⊕a_n s_1s_2...s_i...s_n a1a1⊕a2...a1⊕...⊕ai...a1⊕...⊕ans1s2...si...sn 前缀和的计算用递推得到。普通前缀和的递推公式为 s [ i ] s [ i − 1 ] a [ i ] s[i] s[i-1] a[i] s[i]s[i−1]a[i]异或形式的前缀和递推公式为s[i] s[i-1] ^ a[i]下面代码第11行用这个公式的简化形式求解了前缀和。 代码的计算复杂度是多少第8行和第10行用两重循环遍历所有的子段同时计算前缀和计算复杂度是 O ( n 2 ) O(n^2) O(n2)的可以通过60%的测试。
#includebits/stdc.h
using namespace std;
int main(){int n; cin n;vectorint a(n);for (int i 0; i n; i) cin a[i];long long ans 0;for (int L 0; L n; L) {long sum 0; //sum是包含a[L]的子段的前缀和for (int R L ; R n; R) {sum ^ a[R]; //用递推求前缀和sumans sum; //累加所有子段和}}cout ans endl;return 0;
}3通过100%的测试。 本题有没有进一步的优化方法这就需要仔细分析异或的性质了。根据异或的定义有a⊕a 0、0⊕a a、0⊕0 0。推导子段 a i a j a_i ~ a_j ai aj的异或和 a i ⊕ a i 1 ⊕ . . . ⊕ a j − 1 ⊕ a j ( a 1 ⊕ a 2 ⊕ . . . ⊕ a i − 1 ) ⊕ ( a 1 ⊕ a 2 ⊕ . . . ⊕ a j ) a_i⊕a_{i1}⊕...⊕a_{j-1}⊕a_j (a_1⊕a_2⊕...⊕a_{i-1}) ⊕ (a_1⊕a_2⊕...⊕a_j) ai⊕ai1⊕...⊕aj−1⊕aj(a1⊕a2⊕...⊕ai−1)⊕(a1⊕a2⊕...⊕aj) 记 s i a 1 ⊕ a 2 ⊕ . . . ⊕ a i s_i a_1⊕a_2⊕...⊕a_i sia1⊕a2⊕...⊕ai这是异或形式的前缀和。上式转化为 a i ⊕ a i 1 ⊕ . . . ⊕ a j − 1 ⊕ a j s i − 1 ⊕ s j a_i⊕a_{i1}⊕...⊕a_{j-1}⊕a_j s_{i-1}⊕s_j ai⊕ai1⊕...⊕aj−1⊕ajsi−1⊕sj 若 s i − 1 s j s_{i-1} s_j si−1sj则 s i − 1 ⊕ s j 0 s_{i-1}⊕s_j 0 si−1⊕sj0若 s i − 1 ≠ s j s_{i-1} ≠ s_j si−1sj则 s i − 1 ⊕ s j 1 s_{i-1}⊕s_j 1 si−1⊕sj1。题目要求所有子段异或和相加的结果这等于判断所有的 s i , s j {s_i, s_j} si,sj组合若 s i ≠ s j s_i ≠ s_j sisj则结果加1。 如何判断两个s是否相等可以用位操作的技巧如果它们的第k位不同则两个s肯定不等。下面以 a 1 011 a 2 010 a_1 011a_2 010 a1011a2010为例分别计算第k位的异或和并且相加 k0第0位异或和 s 1 1 s 2 1 ⊕ 0 1 a n s 0 a 1 a 2 a 1 ⊕ a 2 s 1 s 1 ⊕ s 2 s 2 1 0 1 2 s_11s_21⊕01ans_0 a_1a_2a_1⊕a_2 s_1s_1⊕s_2s_2 1012 s11s21⊕01ans0a1a2a1⊕a2s1s1⊕s2s21012 k1第1位异或和 s 1 1 s 2 1 ⊕ 1 0 a n s 1 a 1 a 2 a 1 ⊕ a 2 s 1 s 1 ⊕ s 2 s 2 1 1 0 2 s_11s_21⊕10ans_1 a_1a_2a_1⊕a_2 s_1s_1⊕s_2s_2 1102 s11s21⊕10ans1a1a2a1⊕a2s1s1⊕s2s21102 k2第2位异或和 s 1 0 s 2 0 ⊕ 0 0 a n s 2 a 1 a 2 a 1 ⊕ a 2 s 1 s 1 ⊕ s 2 s 2 0 0 0 0 s_10s_20⊕00ans_2 a_1a_2a_1⊕a_2 s_1s_1⊕s_2s_2 0000 s10s20⊕00ans2a1a2a1⊕a2s1s1⊕s2s20000 最后计算答案 a n s a n s 0 × 2 0 a n s 1 × 2 1 a n s 2 × 2 2 6 ans ans_0 ×2^0 ans_1×2^1 ans_2×2^2 6 ansans0×20ans1×21ans2×226。 本题 0 ≤ A i ≤ 2 20 0≤A_i≤2^{20} 0≤Ai≤220所有的前缀和s都不超过20位。代码第8行逐个计算20位的每一位第11行for循环计算n个前缀和总计算量约为20×n。
#includebits/stdc.h
using namespace std;
int main() {int n; cin n;vectorint a(n);for (int i 0; i n; i) cin a[i];long long ans 0;for(int k0;k20;k){ //所有a不超过20位int zero1,one0; //统计第k位的0和1的数量long long cnt0,sum0; //cnt用于统计第k位有多少对si⊕sj 1for(int i0;in;i){int v(a[i]k)1; //取a[i]的第k位sum ^ v; //对所有a[i]的第k位做异或得到sumsum等于0或者1if(sum0){ //前缀和为0zero; //0的数量加1cnt one; //这次sum0这个sum跟前面等于1的sum异或得1}else{ //前缀异或为1one; //1的数量加1cnt zero; //这次sum1这个sum跟前面等于0的sum异或得1}}ans cnt*(1llk); //第k位的异或和相加}coutans;return 0;
}java代码
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int[] a new int[n];for (int i 0; i n; i) a[i] scanner.nextInt(); long ans 0;for (int k 0; k 20; k) { // 所有a不超过20位int zero 1, one 0; // 统计第k位的0和1的数量long cnt 0, sum 0; //cnt用于统计第k位有多少对si⊕sj 1for (int i 0; i n; i) {int v (a[i] k) 1; // 取a[i]的第k位sum ^ v; // 对所有a[i]的第k位做异或得到sumsum等于0或者1if (sum 0) { // 前缀和为0zero; // 0的数量加1cnt one; // 这次sum0这个sum跟前面等于1的sum异或得1} else { // 前缀异或为1one; // 1的数量加1cnt zero; // 这次sum1这个sum跟前面等于0的sum异或得1}}ans cnt * (1L k); // 第k位的异或和相加}System.out.println(ans);}
}Python代码
n int(input())
a [int(x) for x in input().split()]
ans 0
for k in range(21): # 所有a不超过20位zero, one 1, 0 # 统计第k位的0和1的数量cnt, sum 0, 0 #cnt用于统计第k位有多少对si⊕sj 1for i in range(n):v (a[i] k) 1 # 取a[i]的第k位sum ^ v # 对所有a[i]的第k位做异或得到sumsum等于0或者1if sum 0: # 前缀和为0zero 1 # 0的数量加1cnt one # 这次sum0这个sum跟前面等于1的sum异或得1else: # 前缀异或为1one 1 # 1的数量加1cnt zero # 这次sum1这个sum跟前面等于0的sum异或得1ans cnt * (1 k) # 第k位的异或和相加
print(ans)例4 二维前缀和 前面的例子都是一位数组上的前缀和下面介绍二维数组上的前缀和。 例题领地选择 概况题意在n×m 的矩形中找一个边长为c的正方形把正方形内所有坐标点的值相加使价值最大。 简单的做法是枚举每个坐标作为正方形左上角然后算出边长c内所有地块的价值和找到价值和最高的坐标。时间复杂度 O ( n × m × c 2 ) O(n×m×c^2) O(n×m×c2)能通过60%的测试。请读者练习。 本题是二维前缀和的直接应用。 一维前缀和定义在一维数组a[]上sum[i] a[1] a[2] … a[i] 把一维数组a[]看成一条直线上的坐标前缀和就是所有坐标值的和。 二维前缀和是一维前缀和的推广。设二维数组a[][]有1~n行1~m列二维前缀和 sum[i][j] a[1][1]a[1][2]a[1][3]…a[1][j] a[2][1]a[2][2]a[2][3]…a[2][j] … a[i][1]a[i][2]a[i][3]…a[i][j] 把a[i][j]的(i,j)看成二维平面的坐标那么sum[i][j]就是左下角坐标(1,1)和右上角坐标(i,j)围成的方形中所有坐标点的和。 二维前缀和sum[][]存在以下递推关系 sum[i][j] sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]a[i][j] 根据这个递推关系用两种for循环可以算出sum[][]。 对照上图理解这个公式sum[i-1][j]是坐标(1,1) ~ (i-1, j)内所有的点sum[i][j-1]是(1,1) ~ (i, j-1)内所有的点两者相加其中sum[i-1][j-1]被加了两次所以要减去一次。 C代码
#includebits/stdc.h
using namespace std;
const int N1005;
int a[N][N],s[N][N];
int main() {int n,m,c; cinnmc;for(int i1;in;i)for(int j1;jm;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 Max -130, x, y;for(int x11;x1n-c1;x1)for(int y11;y1m-c1;y1){ //枚举所有坐标点int x2x1c-1,y2y1c-1; //正方形右下角坐标int ans s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]s[x1-1][y1-1];if(ans Max){Max ans;xx1, yy1;}}coutx y\n;return 0;
}Java代码。sum[][]和a[][]可以共用从而节省一半空间。
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int c scanner.nextInt();int[][] a new int[n 1][m 1];for (int i 1; i n; i) {for (int j 1; j m; j) {a[i][j] scanner.nextInt();a[i][j] a[i - 1][j] a[i][j - 1] - a[i - 1][j - 1] a[i][j];}}int Max Integer.MIN_VALUE;int x 0;int y 0;for (int x1 1; x1 n - c 1; x1) {for (int y1 1; y1 m - c 1; y1) {int x2 x1 c - 1;int y2 y1 c - 1;int ans a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] a[x1 - 1][y1 - 1];if (ans Max) {Max ans;x x1;y y1;}}}System.out.println(x y);}
}Python代码
n, m , c map(int, input().split())
a []
a.append([0]*(m1))
for i in range(0, n):a.append([int(k) for k in input().split()])a[i1].insert(0, 0)
for i in range(1, n1):for j in range(1, m1):a[i][j] a[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]
Max float(-inf)
for i in range(1, n2-c):for j in range(1, m2-c):ans a[ic-1][jc-1] - a[ic-1][j-1] - a[i-1][jc-1] a[i-1][j-1]if ans Max:Max ansx iy j
print(x, y)3. 差分 前缀和的主要应用是差分差分是前缀和的逆运算。 与一维数组a[]对应的差分数组d[]的定义 d[k]a[k]-a[k-1] 即原数组a[]的相邻元素的差。根据d[]的定义可以推出 a[k]d[1]d[2]…d[k] 即a[]是d[]的前缀和所以“差分是前缀和的逆运算”。 为方便理解把每个a[]看成直线上的坐标。每个d[]看成直线上的小线段它的两端是相邻的a[]。这些小线段相加就得到了从起点开始的长线段a[]。 差分是一种处理数据的巧妙而简单的方法它应用于区间的修改和询问问题。把给定的数据元素集A分成很多区间对这些区间做很多次操作每次操作是对某个区间内的所有元素做相同的加减操作若一个个地修改这个区间内的每个元素非常耗时。引入“差分数组”当修改某个区间时只需要修改这个区间的“端点”就能记录整个区间的修改而对端点的修改非常容易是O(1)复杂度的。当所有的修改操作结束后再利用差分数组计算出新的A。 为什么利用差分数组能提升修改的效率 把区间[L, R]内每个元素a[]加上v只需要把对应的d[]做以下操作 1把d[L]加上v d[L] v 2把d[R1]减去vd[R1] - v 利用d[]能精确地实现只修改区间内元素的目的而不会修改区间外的a[]值。根据前缀和a[x] d[1] d[2] … d[x]有 11 ≤ x L前缀和a[x]不变 2L ≤ x ≤ R前缀和a[x]增加了v 3R x ≤ N前缀和a[x]不变因为被d[R1]中减去的v抵消了。 每次操作只需要修改区间[L, R]的两个端点的d[]值复杂度是O(1)的。经过这种操作后原来直接在a[]上做的复杂度为O(n)的区间修改操作就变成了在d[]上做的复杂度为O(1)的端点操作。完成区间修改并得到d[]后最后用d[]计算a[]复杂度是O(n)的。m次区间修改和1次查询总复杂度为O(m n)比暴力法的O(mn)好多了。 数据A可以是一维的线性数组a[]、二维矩阵a[][]、三维立体a[][][]。相应地定义一维差分数组D[]、二维差分数组D[][]、三维差分数组D[][][]。
4. 差分例题
例5 差分的基本应用
重新排序 本题的m个查询可以统一处理读入m个查询后每个a[i]被查询了多少次就知道了。用cnt[i]记录a[i]被查询的次数cnt[i]*a[i]就是a[i]对总和的贡献。 下面分别给出70%和100%的两种解法。 1通过70%的测试。 先计算出cnt[]然后第15行算出原数组上的总和ans1。 然后计算新数组上的总和。显然把查询次数最多的数分给最大的数对总和的贡献最大。对a[]和cnt[]排序把最大的a[n]与最大的cnt[n]相乘、次大的a[n-1]与次大的cnt[n-1]相乘等等。代码第18行算出新数组上的总和ans2。 代码的主要计算量是第10行的while和第12行的for复杂度O(mn)只能通过70%的测试。 注意如果把下面第9行的long long改成int那么只能通过30%。
#includebits/stdc.h
using namespace std;
const int N1e53;
int a[N],cnt[N]; //a[]:读入数组cnt[i]第i个数被加的次数
int main(){int n; scanf(%d, n);for(int i1;in;i) scanf(%d, a[i]);int m; scanf(%d, m);long long ans10,ans20; //ans1: 原区间和 ans2: 新区间和while(m--){int L,R; scanf(%d%d, L, R);for(int iL;iR;i)cnt[i]; //第i个数被加了一次累计一共加了多少次
}
for(int i1; in; i) ans1(long long)a[i]*cnt[i]; //在原数组上求区间和sort(a1,a1n);sort(cnt1,cnt1n);for(int i1;in;i) ans2(long long)a[i]*cnt[i];printf(%lld\n, ans2-ans1); //注意 %lld不要写成 %dreturn 0;
}2通过100%的测试。本题是差分优化的直接应用。 前面提到70%的代码效率低的原因是第12行的for循环计算cnt[]。根据差分的应用场景每次查询的[L, R]就是对a[L]~a[R]中的所有数累加次数加1也就是对cnt[L]~cnt[R]中的所有cnt[]加1。那么对cnt[]使用差分数组d[]即可。 C代码。代码第12行用差分数组d[]记录cnt[]的变化第15行用d[]恢复得到cnt[]。其他部分和前面的70%代码一样。 代码的计算复杂度10行的while只有O(n)最耗时的是第17、18行的排序复杂度O(nlogn)能通过100%的测试。
#includebits/stdc.h
using namespace std;
const int N 1e53;
int a[N],d[N],cnt[N];
int main() {int n; scanf(%d, n);for(int i1;in;i) scanf(%d, a[i]);int m; scanf(%d, m);long long ans10,ans20;while(m--){int L,R; scanf(%d%d, L, R);d[L]; d[R1]--;}cnt[0] d[0];for(int i1; in; i) cnt[i] cnt[i-1]d[i]; //用差分数组d[]求cnt[]for(int i1; in; i) ans1 (long long)a[i] * cnt[i];sort(a1,a1n);sort(cnt1,cnt1n);for(int i1; in; i) ans2 (long long)a[i] * cnt[i];printf(%lld\n, ans2-ans1);return 0;
}java代码
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N 100003;int[] a new int[N];int[] d new int[N];int[] cnt new int[N]; int n scanner.nextInt();for (int i 1; i n; i) a[i] scanner.nextInt(); int m scanner.nextInt();long ans1 0, ans2 0;while (m-- 0) {int L scanner.nextInt();int R scanner.nextInt();d[L];d[R1]--;} cnt[0] d[0];for (int i 1; i n; i) cnt[i] cnt[i-1] d[i]; for (int i 1; i n; i) ans1 (long) a[i] * cnt[i]; Arrays.sort(a, 1, n1);Arrays.sort(cnt, 1, n1); for (int i 1; i n; i) ans2 (long) a[i] * cnt[i]; System.out.println(ans2 - ans1);scanner.close();}
}Python代码
N 100003
a [0] * N
d [0] * N
cnt [0] * N
n int(input())
a[1:n1] map(int, input().split())
m int(input())
ans1 0
ans2 0
for _ in range(m):L, R map(int, input().split())d[L] 1d[R1] - 1
cnt[0] d[0]
for i in range(1, n1): cnt[i] cnt[i-1] d[i]
for i in range(1, n1): ans1 a[i] * cnt[i]
a[1:n1] sorted(a[1:n1])
cnt[1:n1] sorted(cnt[1:n1])
for i in range(1, n1): ans2 a[i] * cnt[i]
print(ans2 - ans1)例6 差分的基本应用
推箱子 题解 https://blog.csdn.net/weixin_43914593/article/details/131730112
