定義

累積和(Prefix Sum)は、配列の最初の要素から現在の要素までの和を事前に計算しておき、任意の区間和をO(1)で求められるようにする技法です。

主な特性

• ✓prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
• ✓区間和: sum(l, r) = prefix[r+1] - prefix[l]
• ✓O(n)の前処理後、無限のクエリがO(1)
• ✓2Dに拡張すると部分行列の和もO(1)

時間計算量