差分思想與實(shí)際應(yīng)用
歡迎來到蕭云紋的編程隨筆，本片我們將討論差分思想。
差分思想
差分思想，一個用于優(yōu)化頻繁大區(qū)間修改的思想，具體如下：
設(shè)數(shù)組val、差分?jǐn)?shù)組differ，val存放初始值，而differ[i]存儲的就是val[i]和val[i - 1]的差，所以
??? ?①differ[i] = val[i] - val[i - 1]
???? （當(dāng)i = 0時differ = 0）
根據(jù)①，很容易推出
???? ?②val[i] = differ[0] + differ[1] + ...... +differ[i];
推理過程：展開②等號右側(cè)，即為
???? ?val[i] = 0 + val[1] - val[1]?+ val[2] - val[2] + val[3] + ...... +?val[i - 1] -?val[i - 1] + val[i]
?? ?? ??? ? ??=?val[i]（抵消）
此時，如果我們想使得val數(shù)組的x~y全部加上k，因為val[x+1]~val[y]中每一位數(shù)和它前面的一個數(shù)的差不變，只有val[x],val[y+1]和其前面一位的差改變了，所以使val數(shù)組的x~y全部加上k這個操作和將differ[x]加上k，differ[y + 1]減去k這個效率更高的操作是等價的。
但是如果我們使用差分思想優(yōu)化了區(qū)間的修改效率，使其變成了一個常數(shù)級的操作，但是對val[i]的訪問因為需要使用到②式，使其效率變?yōu)榱薕(i)，這是差分思想的一個劣勢。
不多說了，直接開碼！
題目描述
輸入一串?dāng)?shù)，允許對其進(jìn)行兩個操作：
?操作①：輸入x、y、k，給val[x]~val[y]間的每一個數(shù)字加上k
操作②：輸入i，輸出val[i]的值?
輸入輸出格式
輸入格式：
第一行輸入兩個數(shù)N、M，以空格隔開，分別代表val數(shù)組中數(shù)的個數(shù)，和總操作的個數(shù)。
第二行輸入N個數(shù)，是val數(shù)組每一位的值，下標(biāo)從1開始，以空格隔開。
下面從第3行到第m+三行，輸入命令，命令的格式如下：
操作①：1 x y k。以空格隔開，給val[x]~val[y]間的每一個數(shù)字加上k
操作②：2 i。以空格隔開，輸出val[i]的值
輸出格式：
一共m行，即操作②的結(jié)果（操作①沒有輸出）
輸入輸出樣例
輸入樣例#1：?
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
輸出樣例#1：?復(fù)制
6
10
?
題目解法：
C++代碼，建議先自己思考/寫代碼再閱讀以下部分。
操作①代碼：
inline void Operator1(int *arrayPtr)
{
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
arrayPtr[l] += v;
arrayPtr[r + 1] -= v;
}
操作②代碼：
inline void Operator2(int *arrayPtr)
{
int index, temp = 0;
scanf("%d", &index);
for(int i = 0; i <= index; i++) {
temp += arrayPtr[i];
}
printf("\n%d\n", temp);
}
總體：
#include<bits/stdc++.h>
using namespace std;
?
inline void Operator1(int *arrayPtr)
{
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
arrayPtr[l] += v;
arrayPtr[r + 1] -= v;
}
?
inline void Operator2(int *arrayPtr)
{
int index, temp = 0;
scanf("%d", &index);
for(int i = 0; i <= index; i++) {
temp += arrayPtr[i];
}
printf("\n%d\n", temp);
}
?
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int val[n + 5], differ[n + 5];
differ[0] = 0;
val[0] = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
differ[i] = val[i] - val[i - 1];
}
int oper;
while(m--) {
scanf("%d", &oper);
if(oper == 1) {
Operator1(differ);
}
else {
Operator2(differ);
}
}
return 0;
}
這篇隨筆到此結(jié)束，有什么問題歡迎私信我或者在評論區(qū)提出，我們下次再會。
