报名明年4月蓝桥杯软件赛的同学们，假如你是大一零基础，目前懵懂中，不知该怎么办，可以看看本博客系列：备赛20周合集
20周的完整安排请点击：20周计划
每周发1个博客，共20周（读者可以按自己的进度选“正常”和“快进”两种计划）。
每周3次集中答疑，周三、周五、周日晚上，在QQ群上答疑：
第9周: 前缀和与差分
1. 前缀和概念
前缀和是一种操作简单但是非常有用的优化方法，能把盘算复杂度为O(n)的区间盘算优化为O(1)的端点盘算。
前缀和是出题者喜好稽核的知识点，在算法竞赛中很常见，在蓝桥杯大赛中险些必考。原因有两点：
一是简单，方便在很多场景下应用，与其他考点团结；
二是可以稽核不同层次的能力，例如一道题用暴力法能通过30%的测试，用前缀和优化后能通过70%~100%的测试。
首先了解“前缀和”的概念。一个长度为n的数组a[1] ~ a[n]，前缀和sum即是a[1] ~ a的和：
sum = a[1] + a[2] + … + a
使用递推，可以在O(n)时间内求得所有前缀和：
sum = sum[i-1] + a
假如预盘算出前缀和，就能使用它快速盘算出数组中任意一个区间a ~ a[j]的和。即：
a + a[i+1] + … + 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，每两个相乘即是106，n个数两两相乘，共 n 2 / 2 = 20000 0 2 / 2 = 2 × 1 0 10 n^2/2 = 200000^2/2 = 2×10^{10} n2/2=2000002/2=2×1010次，和S约为 2 × 1 0 10 × 1 0 6 = 2 × 1 0 16 2×10^{10}×10^6 = 2×10^{16} 2×1010×106=2×1016。long long能表示的最大正整数远大于 2 × 1 0 16 2×10^{16} 2×1016，所以不需要用高精度处置处罚大数。
- #include<bits/stdc++.h>
- using namespace std;
- int main() {
- int n; cin >> n; // 读取n
- vector<int> 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−1+n−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/2=2×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_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=(a1+a2+...+an−1)×an+(a1+a2+...+an−2)×an−1+(a1+a2+...+an−3)×an−2+...+(a1+a2)×a3+a1×a2
此中括号内的部分是前缀和 s u m [ i ] = a 1 + a 2 + … + a i sum = a_1+a_2+…+ a_i sum=a1+a2+…+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 S=sum[n−1]×an+sum[n−2]×an−1+sum[n−3]×an−2+...+sum[2]×a3+sum[1]×a2
式子中用到的前缀和sum[1] ~ sum[n-1]，用递推公式sum = sum[i-1] + a做一次for循环就能全部提前盘算出来。
下面的C++代码第8行先预盘算出前缀和sum[]，然后使用sum[]求S。
- #include<bits/stdc++.h>
- using namespace std;
- int main() {
- int n; cin >> n; //读n
- vector<int> a(n+1,0); //定义数组a[]，并初始化为0
- for (int i=1; i<=n; i++) cin >> a[i]; // 读a[1]~a[n]
- vector<long long> sum(n+1, 0); //定义前缀和数组 sum[]，并初始化为0
- for (int i=1; i<n; i++) sum[i]=a[i]+sum[i-1]; // 预计算前缀和sum[1]~sum[n-1]
- long long s = 0;
- for (int i=1; i<n; i++) s += sum[i]*a[i+1]; // 计算和s
- cout << s << endl;
- 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(); // 读n
- int[] a = new int[n+1]; // 定义数组a[]，并初始化为0
- for (int i=1; i<=n; i++) a[i] = scanner.nextInt(); // 读取a[1]~a[n]
- long[] sum = new long[n+1]; // 定义前缀和数组 sum[]，并初始化为0
- for (int i=1; i<n; i++) sum[i]=a[i]+sum[i-1]; // 预计算前缀和sum[1]~sum[n-1]
- long s = 0;
- for (int i=1; i<n; i++) s+=sum[i]*a[i+1]; // 计算和s
- System.out.println(s);
- }
- }
- n = int(input())
- a = [0]+[int(i) for i in input().split()] #读入a[1]~a[n]。a[0]不用
- sum = [0] * (n+1) #定义前缀和
- 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[i+1] #计算和s
- print(s)
可得到的最小取值
第一步肯定是排序，例如从小到大排序，然后再进行两种操作。操作（1）在a[]的尾部选一个数，操作（2）在a[]的头部选2个数。
轻易想到一种简单方法：每次在操作（1）和操作（2）中选较小的值。这是贪心法的思路。但是贪心法对吗？分析之后发现贪心法是错误的，例如{3, 1, 1, 1, 1, 1, 1}，做k=3次操作，每次都按贪心法，做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_{i=1}^{2p}a_i+\sum_{i={n+p-k+1}}^{n}a_i ∑i=12pai+∑i=n+p−k+1nai
为了找最小的和，需要把所有的p都试一遍。假如直接按上面的公式盘算，那么验证一个p的盘算量是O(n)的，验证所有的p，1≤p≤k，总盘算量O(kn)，超时。
轻易发现公式的两个部分就是前缀和，分别即是sum[2p]、sum[n]-sum[n+p-k]。假如提前算出前缀和sum[]，那么验证一个p的时间是O(1)的，验证所有p的总盘算量是O(n)的。
下面是C++代码。注意sum[]需要用long long范例。
代码的盘算复杂度，第10行sort()是O(nlogn)，第13行是O(n)，总复杂度为O(nlogn)。
- #include<bits/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[n+p-k] + s[2*p], ans);
- printf("%lld",ans);
- return 0;
- }
- 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[n+1];
- for (int i = 1; i <= n; i++) a[i] = scanner.nextLong();
- Arrays.sort(a, 1, n+1);
- long[] s = new long[n+1];
- 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[n+p-k] + s[2*p], ans);
- System.out.println(ans);
- }
- }
- n, k = map(int, input().split())
- b = list(map(int, input().split()))
- a=[0] + sorted(b) # a[0]不用，从a[1]开始
- s = [0] * (n+1)
- for i in range(1, n+1): s[i] = s[i-1] + a[i]
- ans = 10**18
- for p in range(1, k+1):
- ans = min(s[n] - s[n+p-k] + s[2*p], ans)
- print(ans)
下面例题是前缀和在异或盘算中的应用，也是常见的应用场景。
异或和之和
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%的测试。
- #include<bits/stdc++.h>
- using namespace std;
- int main(){
- int n; cin >> n;
- vector<int> a(n); //用vector定义数组a[]
- for (int i = 0; i < n; i++) cin >> a[i];
- long long ans=0; //注意这里用long long
- for(int L=0;L<n;L++) //遍历所有区间[L,R]
- for(int R=L;R<n;R++){
- int sum=0;
- for(int i=L;i<=R;i++) sum^=a[i]; //子段和
- ans += sum; //累加所有子段和
- }
- cout<<ans;
- return 0;
- }
记异或和 a 1 ⊕ a 2 ⊕ . . . ⊕ a i a_1⊕a_2⊕...⊕a_i a1⊕a2⊕...⊕ai的前缀和为：
s i = a 1 ⊕ a 2 ⊕ . . . ⊕ a i si=a_1⊕a_2⊕...⊕a_i si=a1⊕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_1+a_1⊕a_2+...+a_1⊕...⊕a_i+...+a_1⊕...⊕a_n = s_1+s_2+...+s_i+...+s_n a1+a1⊕a2+...+a1⊕...⊕ai+...+a1⊕...⊕an=s1+s2+...+si+...+sn
前缀和的盘算用递推得到。普通前缀和的递推公式为 s [ i ] = s [ i − 1 ] + a [ i ] s = s[i-1] + a s=s[i−1]+a，异或形式的前缀和递推公式为s = s[i-1] ^ a，下面代码第11行用这个公式的简化形式求解了前缀和。
代码的盘算复杂度是多少？第8行和第10行用两重循环遍历所有的子段，同时盘算前缀和，盘算复杂度是 O ( n 2 ) O(n^2) O(n2)的，可以通过60%的测试。
- #include<bits/stdc++.h>
- using namespace std;
- int main(){
- int n; cin >> n;
- vector<int> 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]; //用递推求前缀和sum
- ans += sum; //累加所有子段和
- }
- }
- cout << ans << endl;
- return 0;
- }
本题有没有进一步的优化方法？这就需要仔细分析异或的性子了。根据异或的界说，有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_{i+1}⊕...⊕a_{j-1}⊕a_j = (a_1⊕a_2⊕...⊕a_{i-1}) ⊕ (a_1⊕a_2⊕...⊕a_j) ai⊕ai+1⊕...⊕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 si=a1⊕a2⊕...⊕ai，这是异或形式的前缀和。上式转化为：
a i ⊕ a i + 1 ⊕ . . . ⊕ a j − 1 ⊕ a j = s i − 1 ⊕ s j a_i⊕a_{i+1}⊕...⊕a_{j-1}⊕a_j = s_{i-1}⊕s_j ai⊕ai+1⊕...⊕aj−1⊕aj=si−1⊕sj
若 s i − 1 = s j s_{i-1} = s_j si−1=sj，则 s i − 1 ⊕ s j = 0 s_{i-1}⊕s_j = 0 si−1⊕sj=0；若 s i − 1 ≠ s j s_{i-1} ≠ s_j si−1=sj，则 s i − 1 ⊕ s j = 1 s_{i-1}⊕s_j =1 si−1⊕sj=1。标题要求所有子段异或和相加的结果，这即是判定所有的 s i , s j {s_i, s_j} si,sj组合，若 s i ≠ s j s_i ≠ s_j si=sj，则结果加1。
怎样判定两个s是否相当？可以用位操作的技巧，假如它们的第k位不同，则两个s肯定不等。下面以 a 1 = 011 ， a 2 = 010 a_1 = 011，a_2 = 010 a1=011，a2=010为例，分别盘算第k位的异或和，而且相加：
k=0，第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_1=1，s_2=1⊕0=1，ans_0 = a_1+a_2+a_1⊕a_2 = s_1+s_1⊕s_2+s_2 = 1+0+1=2 s1=1，s2=1⊕0=1，ans0=a1+a2+a1⊕a2=s1+s1⊕s2+s2=1+0+1=2
k=1，第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_1=1，s_2=1⊕1=0，ans_1 = a_1+a_2+a_1⊕a_2 = s_1+s_1⊕s_2+s_2 = 1+1+0=2 s1=1，s2=1⊕1=0，ans1=a1+a2+a1⊕a2=s1+s1⊕s2+s2=1+1+0=2
k=2，第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_1=0，s_2=0⊕0=0，ans_2 = a_1+a_2+a_1⊕a_2 = s_1+s_1⊕s_2+s_2 = 0+0+0=0 s1=0，s2=0⊕0=0，ans2=a1+a2+a1⊕a2=s1+s1⊕s2+s2=0+0+0=0
最后盘算答案： 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 ans=ans0×20+ans1×21+ans2×22=6。
本题 0 ≤ A i ≤ 2 20 0≤A_i≤2^{20} 0≤Ai≤220，所有的前缀和s都不高出20位。代码第8行逐个盘算20位的每一位，第11行for循环盘算n个前缀和，总盘算量约为20×n。
- #include<bits/stdc++.h>
- using namespace std;
- int main() {
- int n; cin >> n;
- vector<int> a(n);
- for (int i = 0; i < n; i++) cin >> a[i];
- long long ans = 0;
- for(int k=0;k<=20;k++){ //所有a不超过20位
- int zero=1,one=0; //统计第k位的0和1的数量
- long long cnt=0,sum=0; //cnt用于统计第k位有多少对si⊕sj =1
- for(int i=0;i<n;i++){
- int v=(a[i]>>k)&1; //取a[i]的第k位
- sum ^= v; //对所有a[i]的第k位做异或得到sum，sum等于0或者1
- if(sum==0){ //前缀和为0
- zero++; //0的数量加1
- cnt += one; //这次sum=0，这个sum跟前面等于1的sum异或得1
- }else{ //前缀异或为1
- one++; //1的数量加1
- cnt += zero; //这次sum=1，这个sum跟前面等于0的sum异或得1
- }
- }
- ans += cnt*(1ll<<k); //第k位的异或和相加
- }
- cout<<ans;
- return 0;
- }
- 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 =1
- for (int i = 0; i < n; i++) {
- int v = (a[i] >> k) & 1; // 取a[i]的第k位
- sum ^= v; // 对所有a[i]的第k位做异或得到sum，sum等于0或者1
- if (sum == 0) { // 前缀和为0
- zero++; // 0的数量加1
- cnt += one; // 这次sum=0，这个sum跟前面等于1的sum异或得1
- } else { // 前缀异或为1
- one++; // 1的数量加1
- cnt += zero; // 这次sum=1，这个sum跟前面等于0的sum异或得1
- }
- }
- ans += cnt * (1L << k); // 第k位的异或和相加
- }
- System.out.println(ans);
- }
- }
- 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 =1
- for i in range(n):
- v = (a[i] >> k) & 1 # 取a[i]的第k位
- sum ^= v # 对所有a[i]的第k位做异或得到sum，sum等于0或者1
- if sum == 0: # 前缀和为0
- zero += 1 # 0的数量加1
- cnt += one # 这次sum=0，这个sum跟前面等于1的sum异或得1
- else: # 前缀异或为1
- one += 1 # 1的数量加1
- cnt += zero # 这次sum=1，这个sum跟前面等于0的sum异或得1
- ans += cnt * (1 << k) # 第k位的异或和相加
- print(ans)
前面的例子都是一位数组上的前缀和，下面介绍二维数组上的前缀和。
例题：领地选择
概况题意：在n×m 的矩形中找一个边长为c的正方形，把正方形内所有坐标点的值相加，使价值最大。
简单的做法是罗列每个坐标，作为正方形左上角，然后算出边长c内所有地块的价值和，找到价值和最高的坐标。时间复杂度 O ( n × m × c 2 ) O(n×m×c^2) O(n×m×c2)，能通过60%的测试。请读者练习。
本题是二维前缀和的直接应用。
一维前缀和界说在一维数组a[]上：sum = a[1] + a[2] + … + a
把一维数组a[]当作一条直线上的坐标，前缀和就是所有坐标值的和。
二维前缀和是一维前缀和的推广。设二维数组a[][]有1~n行，1~m列，二维前缀和：
sum[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[1]+a[2]+a[3]+…+a[j]
把a[j]的(i,j)当作二维平面的坐标，那么sum[j]就是左下角坐标(1,1)和右上角坐标(i,j)围成的方形中所有坐标点的和。
二维前缀和sum[][]存在以下递推关系：
sum[j] = sum[i-1][j]+sum[j-1]-sum[i-1][j-1]+a[j]
根据这个递推关系，用两种for循环可以算出sum[][]。
对照上图理解这个公式，sum[i-1][j]是坐标(1,1) ~ (i-1, j)内所有的点，sum[j-1]是(1,1) ~ (i, j-1)内所有的点，两者相加，此中sum[i-1][j-1]被加了两次，所以要减去一次。
C++代码
- #include<bits/stdc++.h>
- using namespace std;
- const int N=1005;
- int a[N][N],s[N][N];
- int main() {
- int n,m,c; 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 Max = -1<<30, x, y;
- for(int x1=1;x1<=n-c+1;x1++)
- for(int y1=1;y1<=m-c+1;y1++){ //枚举所有坐标点
- int x2=x1+c-1,y2=y1+c-1; //正方形右下角坐标
- int ans = s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
- if(ans > Max){
- Max = ans;
- x=x1, y=y1;
- }
- }
- cout<<x<<" "<<y<<"\n";
- return 0;
- }
- 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);
- }
- }
- n, m , c = map(int, input().split())
- a = []
- a.append([0]*(m+1))
- for i in range(0, n):
- a.append([int(k) for k in input().split()])
- a[i+1].insert(0, 0)
- for i in range(1, n+1):
- for j in range(1, m+1):
- 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, n+2-c):
- for j in range(1, m+2-c):
- ans = a[i+c-1][j+c-1] - a[i+c-1][j-1] - a[i-1][j+c-1] + a[i-1][j-1]
- if ans > Max:
- Max = ans
- x = i
- y = j
- print(x, y)
前缀和的主要应用是差分：差分是前缀和的逆运算。
与一维数组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[R+1]减去v：d[R+1] -= v
使用d[]，能准确地实现只修改区间内元素的目的，而不会修改区间外的a[]值。根据前缀和a[x] = d[1] + d[2] + … + d[x]，有：
（1）1 ≤ x < L，前缀和a[x]稳定；
（2）L ≤ x ≤ R，前缀和a[x]增加了v；
（3）R < x ≤ N，前缀和a[x]稳定，由于被d[R+1]中减去的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被查询了多少次就知道了。用cnt记录a被查询的次数，cnt*a就是a对总和的贡献。
下面分别给出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%。
- #include<bits/stdc++.h>
- using namespace std;
- const int N=1e5+3;
- int a[N],cnt[N]; //a[]:读入数组；cnt[i]：第i个数被加的次数
- int main(){
- int n; scanf("%d", &n);
- for(int i=1;i<=n;i++) scanf("%d", &a[i]);
- int m; scanf("%d", &m);
- long long ans1=0,ans2=0; //ans1: 原区间和； ans2: 新区间和
- while(m--){
- int L,R; scanf("%d%d", &L, &R);
- for(int i=L;i<=R;i++)
- cnt[i]++; //第i个数被加了一次，累计一共加了多少次
- }
- for(int i=1; i<=n; i++) ans1+=(long long)a[i]*cnt[i]; //在原数组上求区间和
- sort(a+1,a+1+n);
- sort(cnt+1,cnt+1+n);
- for(int i=1;i<=n;i++) ans2+=(long long)a[i]*cnt[i];
- printf("%lld\n", ans2-ans1); //注意 %lld不要写成 %d
- return 0;
- }
前面提到，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%的测试。
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 1e5+3;
- int a[N],d[N],cnt[N];
- int main() {
- int n; scanf("%d", &n);
- for(int i=1;i<=n;i++) scanf("%d", &a[i]);
- int m; scanf("%d", &m);
- long long ans1=0,ans2=0;
- while(m--){
- int L,R; scanf("%d%d", &L, &R);
- d[L]++; d[R+1]--;
- }
- cnt[0] = d[0];
- for(int i=1; i<=n; i++) cnt[i] = cnt[i-1]+d[i]; //用差分数组d[]求cnt[]
- for(int i=1; i<=n; i++) ans1 += (long long)a[i] * cnt[i];
- sort(a+1,a+1+n);
- sort(cnt+1,cnt+1+n);
- for(int i=1; i<=n; i++) ans2 += (long long)a[i] * cnt[i];
- printf("%lld\n", ans2-ans1);
- return 0;
- }
- 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[R+1]--;
- }
- 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, n+1);
- Arrays.sort(cnt, 1, n+1);
- for (int i = 1; i <= n; i++) ans2 += (long) a[i] * cnt[i];
- System.out.println(ans2 - ans1);
- scanner.close();
- }
- }
- N = 100003
- a = [0] * N
- d = [0] * N
- cnt = [0] * N
- n = int(input())
- a[1:n+1] = map(int, input().split())
- m = int(input())
- ans1 = 0
- ans2 = 0
- for _ in range(m):
- L, R = map(int, input().split())
- d[L] += 1
- d[R+1] -= 1
- cnt[0] = d[0]
- for i in range(1, n+1): cnt[i] = cnt[i-1] + d[i]
- for i in range(1, n+1): ans1 += a[i] * cnt[i]
- a[1:n+1] = sorted(a[1:n+1])
- cnt[1:n+1] = sorted(cnt[1:n+1])
- for i in range(1, n+1): ans2 += a[i] * cnt[i]
- print(ans2 - ans1)
推箱子
题解 https://blog.csdn.net/weixin_43914593/article/details/131730112
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
