いもす法で区間更新を差分にする

すべての区間加算が終わった後の結果だけ必要なら、変化が始まる点と終わる点だけ記録します。

言語：Python / 計算量：O(N+Q)

前提：累積和で区間を引き算にする

考え方

1. [l,r) にxを加えるなら d[l]+=x、d[r]-=x。
2. 最後に左から累積和を取ります。
3. 更新途中に質問する場合は別の構造が必要です。

具体例

長さ5へ [1,4) に2を加えると差分は[0,2,0,0,-2,0]。累積すると[0,2,2,2,0]です。

実装

n=5;d=[0]*(n+1)
d[1]+=2;d[4]-=2
s=0;a=[]
for i in range(n):s+=d[i];a.append(s)
print(a)

注意する条件

右端を含む[l,r]なら打ち消しはr+1です。半開区間の表記と混ぜないでください。

確認問題

長さ5の0配列の[1,4)に2加算。全体和は？

実装課題

N Q と Q 行の l r x。初期値0の長さN配列の[l,r)にxを加える。最終配列を出す。N,Q≤200000、|x|≤10^9。

入力:
5 1
1 4 2
出力:
0 2 2 2 0

n,q=map(int,input().split());d=[0]*(n+1)
for _ in range(q):
    l,r,x=map(int,input().split());d[l]+=x;d[r]-=x
s=0;a=[]
for i in range(n):s+=d[i];a.append(s)
print(*a)

読了の記録・下書き・メモへ