円環上の区間のインデックス

長さ$ Nの数列$ A = (A_0, A_1, \ldots, A_{N - 1})があるとします。

これを円環として見て、$ i番目から始まる長さ$ sの区間について、区間和が求めたいとします。

言い換えると、$ \sum_{j = i}^{i + s - 1} A_{j \bmod N}が求めたいです。

やりかた

$ s \ge Nのときは$ s < Nのときの結果を使って表せるため省略します。

区間を$ [i, \min\{N, i + s\}), [0, \max\{0, i + s - N\}) の２つに分けることで解くことができます。

あとは累積和を使うなどしてください。