?大家好，我是愛分享的小藍(lán)，歡迎交流指正~?
全文目錄??
??差分模板
??差分-樹木上藥
??傳送錨點(diǎn)
???思路點(diǎn)撥
??代碼詳解??
???差分-小明的彩燈
??傳送錨點(diǎn)?
???思路點(diǎn)撥
??代碼詳解?
??差分模板
差分三部曲=差分相減+轉(zhuǎn)換加減+前綴相加
#差分三部曲
#1.差分相減(差分公式)
for i in range(len(dp)-1,0,-1):
dp[i]-=dp[i-1]
#2.轉(zhuǎn)換加減(區(qū)間加減→端點(diǎn)加減)
dp[l-1]+=v
dp[r]-=v
#3.前綴相加(前綴和公式)
for i in range(1,n):
dp[i]+=dp[i-1]
'''
dp=[1, 2, 3, 4, 5, 7, 2]+[0]
首先假設(shè)有一個(gè)數(shù)組：
1 2 3 4 5 7 2
差分后：
1 1 1 1 1 2 -5 -2
一般應(yīng)用場(chǎng)景：
讓你對(duì)區(qū)間 [l,r] 加減操作 N 次
如：
從第二個(gè)元素到第五個(gè)元素每個(gè)+3
從第二個(gè)元素到第四個(gè)元素每個(gè)-2
從第一個(gè)元素到第三個(gè)元素每個(gè)+1
....
這里我們先演示前三個(gè)：
對(duì)于每個(gè) [l,r] 區(qū)間的加減操作都轉(zhuǎn)化為對(duì)端點(diǎn) l,r+1 的操作
從第二個(gè)元素到第五個(gè)元素每個(gè)+3：
轉(zhuǎn)化為：[l]+3 并且 [r+1]-3
那么原序列變成了：
1 1 1 1 1 2 -5 -2
1 4 1 1 1 -1 -5 -2
然后我們按照 a[i]=a[i]+a[i-1] 復(fù)原：
1 5 6 7 8 7 2 0
去掉最后一項(xiàng)，跟原序列對(duì)比：
1 2 3 4 5 7 2
1 5 6 7 8 7 2
確實(shí)是都加上了 3。
我們繼續(xù)操作：
從第二個(gè)元素到第四個(gè)元素每個(gè)-2
轉(zhuǎn)化為：[l]-2 并且 [r+1]+2
那么序列變成了：
1 4 1 1 1 -1 -5 -2
1 2 1 1 3 -1 -5 -2
然后我們按照a[i]=a[i]+a[i-1] 復(fù)原
1 3 4 5 8 7 2 0
與上次復(fù)原后對(duì)比：
1 5 6 7 8 7 2
1 3 4 5 8 7 2
我們最后直接做三次，最后還原：
從第二個(gè)元素到第五個(gè)元素每個(gè)+3
從第二個(gè)元素到第四個(gè)元素每個(gè)-2
從第一個(gè)元素到第三個(gè)元素每個(gè)+1
1 2 3 4 5 7 2
原序列差分后：
2 2 1 0 3 -1 -5 -2
2 號(hào)元素 + 3
6 號(hào)元素 - 3
2 號(hào)元素 - 2
5 號(hào)元素 + 2
1 號(hào)元素 + 1
4 號(hào)元素 - 1
差分序列變成：
2 2 1 0 3 -1 -5 -2
復(fù)原后：
2 4 5 5 8 7 5 0
與原序列對(duì)比：
1 2 3 4 5 7 2
2 4 5 5 8 7 5
'''參考資料：原理解釋 樣例解釋
??差分-樹木上藥
??傳送錨點(diǎn)
???思路點(diǎn)撥
老規(guī)矩，先來一道差集的經(jīng)典例題「樹木上藥」，熟悉一下差分三部曲~
1、差分相減：先創(chuàng)建一個(gè)dp列表，相隔兩個(gè)元素相減。因?yàn)檫@道題dp列表初始化都為0，運(yùn)算之后還是0不變，所以可以跳過第一步不寫，寫上是為了更好理解。
2、轉(zhuǎn)換加減：區(qū)間的加減轉(zhuǎn)換成兩個(gè)端點(diǎn)的加減，左端點(diǎn)加上權(quán)值，右端點(diǎn)減去權(quán)值。
3、前綴相加：將第一步的差集用前綴和還原回去，這里用到之前學(xué)過的前綴和模板。
??代碼詳解??
#差分-樹木打藥
n,m=map(int, input().split())
dp=[0]*n
#1.差分相減(差分公式)
#可以跳過不寫
#2.轉(zhuǎn)換加減(區(qū)間加減→端點(diǎn)加減)
for i in range(m):
l,r,v= map(int, input().split())
dp[l-1]+=v #l的下標(biāo)是l-1
dp[r]-=v #r+1的下標(biāo)是r
#3.前綴相加(前綴和公式)
for i in range(1,n):
dp[i]+=dp[i-1]
print(sum(dp))
'''
input:
500 3
150 300 4
100 200 20
470 471 19
print:
2662
'''
???差分-小明的彩燈
??傳送錨點(diǎn)
???思路點(diǎn)撥
接下來，一道差集的簡(jiǎn)單題「小明的彩燈」，檢驗(yàn)一下差分三部曲的掌握情況吧~
1、差分相減：先創(chuàng)建一個(gè)dp列表，差分相減直接跳過。
2、轉(zhuǎn)換加減：區(qū)間彩燈的亮度加減，轉(zhuǎn)化為兩個(gè)端點(diǎn)的亮度加減。
3、前綴相加：前綴和還原回去，就完成差分模板了。文章來源：http://www.zghlxwxcb.cn/news/detail-807441.html
??代碼詳解??
#差分-小明的彩燈
n,q=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+1)
for i in range(q):
l,r,x=map(int,input().split())
dp[l-1]+=x
dp[r]-=x
for i in range(1,n):
dp[i]+=dp[i-1]
for i in range(n):
print(max(dp[i]+a[i],0),end=" ")
'''
input:
5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100
print:
0 5 5 6 10
'''??????友友們，備戰(zhàn)藍(lán)橋最后3天，一起沖刺省賽一等獎(jiǎng)！???
??文章來源地址http://www.zghlxwxcb.cn/news/detail-807441.html
到了這里，關(guān)于【藍(lán)橋模板】——考試倒計(jì)時(shí)3天，你和省一就差這最后10分了（差分模板）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
