◉ 累積和
Kyopro Encyclopedia of Algorithms

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /cumulative-sum#noredirect を利用してください。

このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /cumulative-sum#noredirect を利用してください。

name: 累積和
short description: 累積和とは、ある数列の接頭辞の総和たちを要素とする数列のこと。長さ $N$ の数列 $a = (a_0, a_1, \dots, a _ {N - 1})$ に対する累積和とは $b_i = \sum _ {j \lt i} a_i$ であるような長さ $N + 1$ の数列 $b$ である。数列の要素が群の要素であるときには区間 $\lbrack l, r)$ の総和 $\sum _ {i \in \lbrack l, r)} a_i = b_r - b_l$ を $O(1)$ で計算することなどに用いることができる。
input: 長さ $N$ の数列 $a$
output: 長さ $N + 1$ の数列 $b$ (ただし $b_i = \sum _ {j \lt i} a_i$)
time complexity: 構築に $O(N)$ で利用に $O(1)$
space complexity: $O(N)$

話題

changelog

license