【備忘録】累積和

あくまで備忘録なんで雑に記録します

①累積和の図
練習
累積和def

①累積和の図

累積和がなぜ良いのかはなんとなく分かったのですが、実用する時のイメージ図を備忘録として
（複数回演算すると時間がかかるから、前処理としてのSリストを作っておくと、S(Right)ーS(Left)でO(1)で出せる：クエリ）

注意点①aは０〜 n-1

注意点②sは０〜ｎ

注意点③S.append(s)は先に加える（↓）

n = 6
A = [5, 11, 1, 8, 7, 2]

S = []
s = 0
S.append(s)#まずs0加える

for i in range(n):#s1~s6まで加える
    s += A[i]
    S.append(s)
print(S)
#累積和S[0, 5, 16, 17, 25, 32, 34]
#部分和 [a1,a4)
print(S[4]-S[1])
#20

練習

AtCoder Beginner Contest 129　B – Balance
AtCoder Beginner Contest 129　B – Balance

問題文
1からNの番号がついたN個の重りがあり、番号iの重りの重さはWiです。
ある整数 1≤T<Nに対してこれらの重りを、番号がT以下の重りと番号がTより大きい重りの2グループに分けることを考え、それぞれのグループの重さの和をS1,S2とします。
このような分け方全てを考えた時、S1とS2の差の絶対値の最小値を求めてください。

N = 6
W = [5, 11, 1, 8, 7, 2]

S = []
s = 0
S.append(s)#まずs0加える

for i in range(N):#s1~s6まで加える
    s += W[i]
    S.append(s)
#[0, 5, 16, 17, 25, 32, 34]
#1<=T<Nなので、（a6は本当はないけど、)未満の都合上、その為にSリストは＋１）
#T＝１・・・境界線は、a0とa1の間　[a0, a1)と[a1, a6)　〜
#T＝５・・・境界線は、a4とa5の間　[a0, a5)と[a5, a6)

#abs((S[1]-S[0])-(S[6]-S[1]))　〜
#abs((S[5]-S[0])-(S[6]-S[5]))

ans = float('inf')
for j in range(N-1):
    S1 = S[j+1]-S[0]#左側
    S2 = S[N]-S[j+1]#右側
    if ans >= abs(S1 - S2):
        ans = abs(S1 - S2)
print(ans)

累積和def

# 累積和：
n = 10
A = [i for i in range(1, n+1)]#nとA要素数は一致させる
print(A)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def Accumulation(A_list, N_count):
    S = []
    s = 0
    S.append(s)#まずs0を入れとく
    for i in range(N_count):
        s += A_list[i]#解釈するとs(i+1)=s(i)+a(i)
        S.append(s)
    return S

print(Accumulation(A, n))#[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]



'''最初の部分
a    a0
s s0 s1

s0=0
s1=0+a0
s2=0+a0+a1 = s1+a1

[ A[3], A[6] )　の部分累積和
A[3] = 4
A[6] = 7　という事で、4+5+6=15
S[6]はA[5]までの累積、S[3]はA[2]までの累積、[ A[3], A[6] ) は A[3]〜A[5]つまり、S[6]-S[3]
'''
print(Accumulation(A, n)[6]-Accumulation(A, n)[3])#15