累積和

累積和の理解とそのプログラム

###前提
　この記事は、自分で何とか理解したものを、偉そうに書き下しているだけです。下に書いてあることは参考程度にしてください
また、もし何かアドバイスや指摘がありましたら遠慮なくおねがいします、成長になります。

まず初めに

　累積和にはいろいろな形の累積和がある。自分が学習した基本的な累積和の考え方を共有したいと思う。
　累積和は、たとえば、いろいろな長さの紐があるときに、5cm ~ 7cmの紐の個数を求めるみたいな処理を何度もするときに、あらかじめ数えておくことによって、その後の処理を高速化するものである。
　今回、まとめていきたいのは、累積和を使うときに自分がよくindexの処理にてこずるので、それらを整理していきたい

理解

​まずはリストAについてA_l + A_(l+1) + ... + A_(r-1)の区間和を求めるプログラムを見ていこう

n = int(input())
A = list(map(int, input().split()))

#累積和
total = [0] * (n + 1)
for i in range(1, n + 1):
    total[i] = total[i - 1] + A[i - 1]

#区間和処理
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(total[r] - total[l])

このプログラムの説明

• 累積和の処理について
  total[i]はiコ目までの総和

• 区間処理について
  A_l + A_(l+1) + ... + A_(r-1)をもとめるとき

A_l + A_(l+1) + ... + A_(r-1) = (A_(r-1) + ... + A_0) - (A_(l-1) + ... + A_0)
とすると、これはtotal[r] - total[l]で表すことができる
つまり、あらかじめ累積和totalを作っておくことにより、いちいち区間和を計算し直すのではなくO(1)で高速な処理が可能になっていることがわかる

では、以上を利用して、次の問題に取り組んでみる
https://algo-method.com/tasks/1679i9so

この問題は最初の例にも挙げたように、欲しい長さのひもをすぐに取り出せるように、ひもを長さで検索できるプログラムだ

まず、求めたいものは、「長さが A以上B以下(A,Bは整数)であるようなひもの本数」である
つまり、「長さB以下の紐の本数から、A未満の紐の本数を除く」ということなので、total[i]を長さi以下の紐の本数として累積和をつくると、答えは
total[b] - total[a - 1]となることがわかる
ここからさらに、今回total[i]のiはありうるどんな紐の長さにも対応しなければならない
以上をプログラムにすると以下だ

n = int(input())
L = list(map(int,input().split()))

#ありうる紐の長さは10 ** 5まで
counter = [0] * (10 ** 5 + 1)
for l in L:
    counter[l] += 1

# 長さ5のひもがあって、長さ5以下のひもの本数が3本だとする
# 次のひもの長さが10のとき、間の長さ6,7,8,9以下のひもの本数は3本なので
# 伝播の処理が必要になる
for i in range(1, 10 ** 5 + 1):
    counter[i] += counter[i - 1]

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    print(counter[b] - counter[a - 1])

*** まとめ
累積和はindexの処理がたまにわからなくなることがあるが、基礎をおさえて丁寧に考えれば意外といけるかも
いもす法などについても今後学習していきたい