課堂學習
前綴和數組
前1個收購點：3箱
前2個收購點：3+2=5箱
前3個收購點：3+2+5=10箱
以此類推…
數組a存儲10個收購點的箱數。
收購點編號從1~10，數組下標也從1開始使用。
下標0位置直接賦值0
#include<bits/stdc++.h>
using namespace std;
int main(){//創建并初始化數組a：從下標1開始用，下標0賦值0int a[11]={0,3,2,5,6,6,1,4,1,7,3};//創建并初始化數組sint s[11]={};//1.初始條件：s[1]=a[1]s[1]=a[1];//2.根據遞推關系推導前綴和：s[i]=s[i-1]+a[i] (i>=2)for(int i=2;i<=10;i++){s[i]=s[i-1]+a[i];}//3.循環輸出前綴和for(int i=1;i<=10;i++){cout<<s[i]<<" ";}return 0;
}課堂訓練
2915?計算區間和
描述
輸入?n?個整數，再輸入m個區間，每個區間的起點下標L，終點下標R。
對于每個區間，輸出n個整數中從下標L到下標R的區間和。
輸入描述
第一行包括兩個整數n和m。（1≤n,m≤500000）
第二行包括n個整數。（1≤整數≤100）
接下來有m行，每行包含兩個整數L和R，表示區間范圍。（0<L≤R≤n）
輸出描述
輸出有m行，每行一個整數，表示一個區間和。
樣例輸入 1?
10 3 2 1 3 6 4 20 15 10 4 11 3 7 1 9 5 8
樣例輸出 1?
48 65 49
簡單分析
//2915 計算區間和
#include<bits/stdc++.h>//萬能頭文件
using namespace std;
const int N=500010;
int a[N],s[N];//a是原數組，s是前綴和數組
int main(){//輸入數據int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}s[1]=a[1];//求出任意位置的前綴和for(int i=2;i<=n;i++){s[i]=s[i-1]+a[i];}int L,R;for(int i=1;i<=m;i++){cin>>L>>R;cout<<s[R]-s[L-1]<<endl;}return 0;
}練一練：?
總結：前綴和
③前綴和優勢：可以1步減法算出區間和。
下標[L~R]的區間和=s[R]-s[L-1]
④前綴和使用場景：多次計算區間和。
注意：區間起點L一般從1開始。
如果L=0,就會導致s[L-1]為s[-1]的情況。?
2916?K個元素和
描述
輸入n個整數，求出所有連續且長度為K的元素總和。
輸入描述
第一行包括兩個整數n和K。（1≤K≤n≤500000）
第二行包括n個整數。（1≤整數≤100）
輸出描述
輸出一行，包含若干數字，每個數字表示1個元素總和。
樣例輸入 1?
10 3 2 1 3 6 4 5 8 7 0 9
樣例輸出 1?
6 10 13 15 17 20 15 16
提示
根據樣例得知，在10個數字中求連續且長度為3的元素總和，依次得到：
2+1+3=6；1+3+6=10；3+6+4=13；6+4+5=15；
4+5+8=17; 5+8+7=20; 8+7+0=15; 7+0+9=16。
#include<bits/stdc++.h>
using namespace std;
int a[500010]={};//原數組
int s[500010]={};//前綴和數組
int main(){int n,K;cin>>n>>K;//1.輸入n個元素; 注意從下標1開始使用for(int i=1;i<=n;i++){cin>>a[i];}//2.循環推導前綴和s[1]=a[1];for(int i=2;i<=n;i++){s[i]=s[i-1]+a[i];}//3.遍歷所有長度K的區間；計算輸出區間和for(int i=K;i<=n;i++){cout<<s[i]-s[i-K]<<" ";}return 0;
}4434?m倍的區間
描述
輸入?n?個整數，在所有連續且長度為?K?的區間中，統計有多少區間和是?m?的倍數。
輸入描述
第一行包括三個整數?n，K?和?m。
第二行包括?n?個整數。
輸出描述
輸出一個整數，表示有多少個區間和是?m?的倍數。
樣例輸入 1?
5 3 2 2 1 3 6 4
樣例輸出 1?
2
提示
1≤m≤K≤n≤500000，1≤整數≤100
長度為3的區間有：2 1 3，1 3 6，3 6 4。
區間2 1 3和1 3 6的和是2的倍數。
#include<bits/stdc++.h>
using namespace std;
int a[500010]={};//原數組
int s[500010]={};//前綴和數組
int main(){int n,k,m;cin>>n>>k>>m;for(int i=1;i<=n;i++){cin>>a[i];}//推導前綴和數組s[1]=a[1];for(int i=2;i<=n;i++){s[i]=s[i-1]+a[i];}int ans=0;//遍歷所有長度K的區間for(int i=k;i<=n;i++){int t=s[i]-s[i-k]; //計算區間和if(t%m==0){ //判斷區間和是m倍數ans++;}}cout<<ans;return 0;
}4433?最大區間和
描述
輸入?n?個整數，在所有連續且長度為K的區間中，找到最大的區間和。
輸入描述
第一行包括兩個整數?n?和?K。
第二行包括?n?個整數。
輸出描述
輸出兩行。第一行一個整數，表示最大區間和。
第二行兩個整數，表示最大區間和的起點下標和終點下標。
樣例輸入 1?
10 3 2 1 3 6 4 5 8 7 5 3
樣例輸出 1?
20 6 8
提示
1≤K≤n≤500000，1≤整數≤100
樣例中最大區間下標范圍：6~8，區間和為20。
注意：如果多個區間和同為最大，取第1個區間。
#include<bits/stdc++.h>
using namespace std;
int a[500010]={};//原數組
int s[500010]={};//前綴和數組
int main(){int n,K;cin>>n>>K;//1.輸入n個元素; 注意從下標1開始使用for(int i=1;i<=n;i++){cin>>a[i];}//2.循環推導前綴和s[1]=a[1];for(int i=2;i<=n;i++){s[i]=s[i-1]+a[i];}//3.遍歷所有長度K的區間//先計算區間和，再取最大的區間和int res=0;//最大區間和int b,e;//起點下標b，終點下標efor(int i=K;i<=n;i++){//終點下標:i//起點的前1個下標:i-Kint t=s[i]-s[i-K];if(t>res){res=t;b=i-K+1;e=i;}}//4.輸出結果cout<<res<<endl;cout<<b<<" "<<e<<endl;return 0;
}差分
練一練?
差分性質
差分理論?
4436?混合操作
描述
輸入?n?個整數，計算區間和。
輸入描述
第一行包括一個整數?n。
第二行包括?n?個整數。
第三行包括一個整數?m，表示需進行?m?次操作。
操作包括兩種：1?表示計算區間和；2?表示修改?n?個整數的其中?1?個。（操作?2?只有?1?次）
接著有?m?行，每行表示?1?次操作：
如果第一個數字為?1，后面跟著區間的起點?L，終點?R；
如果第一個整數為?2，后面跟著被修改整數所在位置?k，修改為整數?num。
輸出描述
輸出?m?1?行，每行一個整數，表示一個區間和。
樣例輸入 1?
10 2 1 3 6 4 20 15 10 4 11 5 1 3 7 1 4 9 2 8 20 1 7 10 1 5 8
樣例輸出 1?
48 59 50 59
提示
1≤n≤100000，1≤整數≤100，1≤m≤100000
對?10?個整數做?5?次操作：
第1次：計算[3~7]區間和，結果48；
第2次：計算[4~9]區間和，結果59；
第3次：修改第8個數字10，修改為20；
第4次：計算[7~10]區間和，結果50；
第5次：計算[5~8]區間和，結果59。
#include<bits/stdc++.h>
using namespace std;
int a[100010]={}; //原數組
int s[100010]={}; //前綴和數組
int main(){int n,m;cin>>n;//1、輸入n個整數for(int i=1;i<=n;i++) cin>>a[i];//2、推導前綴和s[1]=a[1];for(int i=2;i<=n;i++) s[i]=s[i-1]+a[i];//3、遍歷m次操作，判斷并處理cin>>m;int c;//操作標記int L,R;int k,num;for(int i=1;i<=m;i++){ //m次操作cin>>c;if(c==1){ //計算區間和cin>>L>>R;cout<<s[R]-s[L-1]<<endl;}else{ //修改一個整數cin>>k>>num;a[k]=num; //元素a[k]賦值num//重新計算前綴和s[1]=a[1];for(int j=2;j<=n;j++) s[j]=s[j-1]+a[j];}}return 0;
}?課后作業
2919?最要強的飛行員
描述
在一次電子模擬作戰中，假設敵方設置了一條防線，防線上依次有n個據點。每個據點都有一個牢固值，數值越大表示越牢固。
司令部計劃對n個據點進行m輪攻擊，每輪攻擊一段連續范圍的據點，每段范圍上的據點都存在一個總牢固值。
有一位最要強的飛行員，申請在總牢固值最大的一輪出戰。
請你編寫程序找到最大的總牢固值。
輸入描述
第一行包括兩個整數n和m。（1≤n,m≤500000）
第二行包括n個整數，依次表示n個據點的牢固值。（1≤整數≤100）
接下來m行，每行兩個正整數L和R，表示一輪范圍。（1≤L≤R≤n）
輸出描述
輸出一個整數，表示最大的總牢固值。
樣例輸入 1?
7 2 2 10 5 3 6 4 9 3 5 6 7
樣例輸出 1?
14
提示
輸入樣例中m=2，表示有2輪攻擊。
第1輪攻擊從3~5，總牢固值5+3+6=14。
第2輪攻擊從6~7，總牢固值4+9=13。
兩輪攻擊總牢固值最大14。
#include<bits/stdc++.h>
using namespace std;
int a[500001],s[500001];
int main(){int n,m;int L,R,res=0;//res存儲最大總牢固值cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];//輸入據點牢固值s[i]=s[i-1]+a[i];//計算該據點前綴和}for(int i=1;i<=m;i++){cin>>L>>R;//輸入一輪打擊范圍if((s[R]-s[L-1])>res){ //判斷當前據點總牢固值是否大于resres=s[R]-s[L-1];}}cout<<res;//輸出最大總牢固值resreturn 0;
}2939?紙牌PK
描述
小童和小程每次遇到誰優先的問題，都會采用抽一張紙牌比大小的方式決定，總采用這種方式，難免感到無趣。
小童今天突發奇想，修改了抽紙牌的方式。修改后的方式是這樣的：兩人輪流在n張紙牌中抽取m輪，每輪抽取連續一定范圍的紙牌，計算m輪抽取中所有牌面上的數字總和，最終誰的數字總和大，誰獲得優先權。
輸入描述
第一行包括兩個整數n和m。（1≤m,n≤500000）（1≤m≤100）
第二行包括n個整數，依次表示n張紙牌上的數字。（1≤整數≤100）
接下來m行，每行兩個正整數L和R，表示小童每輪抽牌的范圍。
接下來m行，每行兩個正整數L和R,表示小程每輪抽牌的范圍。（1≤L≤R≤n）
輸出描述
輸出一個字符，小童數字總和大，輸出T；小程數字總和大，輸出C；總和相等輸出D。
樣例輸入 1?
7 3 2 10 5 3 6 4 9 3 5 6 7 2 7 2 6 1 2 1 6
樣例輸出 1?
C
提示
輸入樣例中m=3，表示兩人各自抽3輪范圍紙牌。
小童第1輪：抽取第3~5張紙牌，該輪數字和5+3+6=14。
小童第2輪：抽取第6~7張紙牌，該輪數字和4+9=13。
小童第3輪：抽取第2~7張紙牌，該輪數字和10+5+3+6+4+9=37。
小童數字總和14+13+37=64。
小程第1輪：抽取第2~6張紙牌，該輪數字和10+5+3+6+4=28。
小程第2輪：抽取第1~2張紙牌，該輪數字和2+10=12。
小程第3輪：抽取第1~6張紙牌，該輪數字和2+10+5+3+6+4=30。
小程數字總和28+12+30=70。
最終小程數字總和大于小童，輸出字符C。
#include<bits/stdc++.h>
using namespace std;
int a[500001],s[500001];
int main(){int n,m;long long sum_t=0,sum_c=0;int L,R;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i]; //計算前綴和}for(int i=1;i<=m;i++){cin>>L>>R;sum_t=sum_t+(s[R]-s[L-1]); //用前綴和計算范圍紙牌總和；并累加}for(int i=1;i<=m;i++){cin>>L>>R;sum_c=sum_c+(s[R]-s[L-1]); //用前綴和計算范圍紙牌總和；并累加}if(sum_t>sum_c){//小童m輪紙牌總數大cout<<'T';}else if(sum_t<sum_c){//小程m輪紙牌總數大cout<<'C';}else{//平局cout<<'D';}return 0;
}2918?物資準備
描述
某國測試一種新型火炮，對一條路線進行打擊。
這條路線上有n個據點，每個據點都有一個牢固值，1發炮彈消耗1點牢固值，假設牢固值為10的據點，需要10發炮彈摧毀。
現在共有m門火炮參與測試，每門火炮摧毀一段連續范圍的據點。
由于指揮混亂，m門火炮發射前沒有溝通，可能存在炮彈浪費的情況。
問合計需要準備多少發炮彈。
輸入描述
輸入描述
第一行包括兩個整數n和m。（1≤n,m≤100000）
第二行包括n個整數，依次表示n個據點的牢固值。（1≤整數≤100）
接下來m行，每行兩個正整數L和R，表示一門火炮的摧毀范圍。（1≤L≤R≤n）
輸出描述
輸出一個整數，表示炮彈總數。
樣例輸入 1?
7 2 2 10 5 3 6 4 9 3 5 6 7
樣例輸出 1?
27
樣例輸入 2?
5 3 4 2 10 3 7 1 2 4 5 1 3
樣例輸出 2?
32
提示
路線上有?7?個據點，2?門火炮參與。
7個據點的牢固值依次為：2，10，5，3，6，4，9。
第1門火炮摧毀第3，4，5據點，需發射炮彈數量：5+3+6=14。
第2門火炮摧毀第6，7據點，需發射炮彈數量：4+9=13。
合計需要準備?27?發炮彈。
路線上有?5?個據點，3?門火炮參與。
5個據點的牢固值依次為：4，2，10，3，7。
第1門火炮摧毀第1，2據點，需發射炮彈數量：4+2=6。
第2門火炮摧毀第4，5據點，需發射炮彈數量：3+7=10。
第3門火炮摧毀第1，2，3據點，需發射炮彈數量：4+2+10=16。（無需考慮炮彈浪費的情況）
合計需要準備?32?發炮彈。
#include<bits/stdc++.h>
using namespace std;
int a[100010]; //原數據
int s[100010]; //前綴和
int main(){int n,m;cin>>n>>m;//輸入原數據for(int i=1;i<=n;i++) cin>>a[i];//計算前綴和ss[1]=a[1];for(int i=2;i<=n;i++) s[i]=s[i-1]+a[i];//總數 注意總數會超過int范圍，用long long類型long long sum=0;for(int i=1;i<=m;i++){int L,R;cin>>L>>R;sum+=(s[R]-s[L-1]);}cout<<sum;return 0;
}3212?有趣的求和
描述
給出n個數排成一排，你可以任意選出連續的L個數字求和。例如：
n=5 L = 4
-20 30 80 50 40
連續取L個數的方法有兩種。
1、取前4個數-20 30 80 50 和為140。
2、取后4個數30 80 50 40 和為200。
請你找出最大和是多少，上例結果應該為200。
輸入描述
第1行為兩正整數n和L表示數列數字個數和取的長度；
第2行n個整數空格分隔，表示數列中的每個元素，數字在-100到100之間的整數。
輸出描述
輸出一個整數，最大的數字和。
樣例輸入 1?
5 4 -20 30 80 50 40
樣例輸出 1?
200
提示
30%的數據1≤L≤n≤100。
50%的數據1≤L≤n≤10000。
100%的數據 1≤L≤n≤1000000。
#include<bits/stdc++.h>
using namespace std;
int a[1000001],s[1000001];
int main(){int n,l;cin>>n>>l;for(int i=1;i<=n;i++) cin>>a[i];//計算前綴和s[1]=a[1];for(int i=2;i<=n;i++) s[i]=s[i-1]+a[i];//創建變量存儲最大數字和//初始化成比可能出現的最小值還小int max1=-1000000000;for(int i=l;i<=n;i++){if(max1<s[i]-s[i-l]) max1=s[i]-s[i-l];}cout<<max1;return 0;
}
