累積和とランニングトータル
O(1)で区間和のクエリに答えられる累積和配列を作り、最大和部分配列などの部分配列問題に応用します。
「累積和とランニングトータル」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
範囲和問題
配列 nums が与えられたとき、インデックス i からインデックス j までの要素の合計はいくつかという形式のクエリに何度も答える必要があるとします。各クエリを単純に処理すると O(n) かかるため、k 個のクエリでは O(n×k) かかります。累積和配列を使えば、累計値を O(n) で前計算し、その後の各クエリに O(1) で答えられます。これは面接で最も広く使われる前計算テクニックの 1 つです。
# Naive: O(n) per query
def range_sum_naive(nums, i, j):
return sum(nums[i:j+1])
nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3)) # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4)) # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operations累積和配列の構築
prefix[i] を nums[0] から nums[i-1] までの合計として定義します（要素を 1 つ多く確保し、0 始まりのインデックスに 1 のオフセットを設けることで、境界ケースを扱いやすくします）。1 回の走査で prefix[i] = prefix[i-1] + nums[i-1] を計算すれば、O(n) で構築できます。すると、範囲クエリ sum(i, j) は prefix[j+1] - prefix[i] となり、O(1) の単一の減算で求められます。
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, i, j):
return prefix[j+1] - prefix[i] # O(1)
nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre) # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3)) # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15 correct
print(range_sum(pre, 1, 3)) # 15和が K になる部分配列
合計が k に等しい部分配列の個数を求める問題は、ハッシュマップと累積和を組み合わせる典型的な問題です。重要なポイントは、i から j までの部分配列の和が prefix[j] - prefix[i-1] で表せることです。これを k と等しくしたい場合、prefix[i-1] = prefix[j] - k となります。左から右へ走査しながら累積和を保持し、current_sum - k がそれまでに何回現れたかを調べることで、すべての有効な部分配列を合計 O(n) で数えられます。
from collections import defaultdict
def subarray_sum_k(nums, k):
count = 0
current = 0
freq = defaultdict(int)
freq[0] = 1 # empty prefix
for n in nums:
current += n
count += freq[current - k] # how many prior sums give diff=k
freq[current] += 1
return count
print(subarray_sum_k([1, 1, 1], 2)) # 2
print(subarray_sum_k([1, 2, 3], 3)) # 2 ([1,2] and [3])累積和による最大部分配列和
最大部分配列和は、累積和の問題として捉えることができます。各インデックス j について、すべての i < j に対する prefix[j] - prefix[i] を最大化します。各 j で最適な i となるのは、それまでに見た累積和の最小値です。左から右へ走査しながら min_prefix を記録すると、時間計算量 O(n) になります。これは、累積和の観点から見た Kadane's algorithm と同じものです。
def max_subarray_prefix(nums):
max_sum = float('-inf')
min_pre = 0 # prefix[0] = 0
current = 0
for n in nums:
current += n
max_sum = max(max_sum, current - min_pre)
min_pre = min(min_pre, current)
return max_sum
print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6 (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1グリッドクエリのための 2D 累積和
累積和は 2D グリッドにも拡張できます。P[i][j] を、(0,0) から (i-1,j-1) までの長方形内にあるすべての要素の合計として定義します。包除原理の式 P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1] を使って構築します。すると、(r1,c1) から (r2,c2) までの任意の長方形の和を、4 回の参照によって O(1) で求められます。
def build_2d_prefix(grid):
R, C = len(grid), len(grid[0])
P = [[0]*(C+1) for _ in range(R+1)]
for r in range(1, R+1):
for c in range(1, C+1):
P[r][c] = (P[r-1][c] + P[r][c-1]
- P[r-1][c-1] + grid[r-1][c-1])
return P
def rect_sum(P, r1, c1, r2, c2):
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1)) # 3+0+5+6 = 14平衡インデックスのための累計値
平衡インデックスとは、左側の要素の合計と右側の要素の合計が等しくなる位置です。まず合計を前計算し、その後、左側の累計値を保持しながら走査します。右側の合計は total - left_sum - nums[i] です。各インデックスで O(1) で等しいかを確認できるため、全体の計算量は O(n) になります。これは、2 つの別々の累積和配列を累計値 1 つで置き換える方法を示しています。
def find_pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, n in enumerate(nums):
# right_sum = total - left_sum - nums[i]
if left_sum == total - left_sum - n:
return i
left_sum += n
return -1
print(find_pivot_index([1, 7, 3, 6, 5, 6])) # 3
print(find_pivot_index([1, 2, 3])) # -1自分以外の積の配列
配列が与えられたとき、各要素をそれ以外のすべての要素の積に置き換えた配列を返します。除算は使えません。前方の積と後方の積を使います。result[i] = （i より前にあるすべての要素の積）×（i より後にあるすべての要素の積）です。左から右への走査で前方の積を構築し、その後、累積変数を使って右から左への走査で後方の積を掛け合わせます。後方の積用に別の配列を用意する必要はありません。
def product_except_self(nums):
n = len(nums)
result = [1] * n
# Left pass: result[i] = product of nums[:i]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right pass: multiply in product of nums[i+1:]
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6] O(n) time, O(1) extra space余りを使った累積和
合計が k で割り切れる部分配列の個数を求める問題があります。累積和を k で割った余りを使うと、prefix[j] % k == prefix[i] % k の場合、sum(i+1..j) は k で割り切れます。走査中に各余りの出現回数をハッシュマップで数えると、時間計算量 O(n) で求められます。インデックス 0 から始まる部分配列を処理するために、freq[0] = 1 と初期化することが重要です。
from collections import defaultdict
def subarray_div_by_k(nums, k):
freq = defaultdict(int)
freq[0] = 1
current = 0
count = 0
for n in nums:
current = (current + n) % k
count += freq[current]
freq[current] += 1
return count
print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7 (seven subarrays divisible by 5)範囲更新のための差分配列
差分配列は累積和の逆です。配列が与えられたとき、diff[i] = nums[i] - nums[i-1] を前計算します。範囲 [l, r] に x を加えるには、差分配列に対して O(1) の操作を 2 回行うだけです。diff[l] += x と diff[r+1] -= x を実行します。すべての更新が終わったら、1 回の累積和の走査で結果の配列を再構築します。これにより、k 回の範囲更新を O(n×k) から O(n + k) にできます。
def apply_range_updates(n, updates):
# updates: list of (l, r, val)
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r+1] -= val
# Reconstruct with prefix sum
result = []
running = 0
for i in range(n):
running += diff[i]
result.append(running)
return result
# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]面接問題における累積和
累積和は、さまざまな種類の問題に登場します。
- 範囲クエリ — 部分配列の和、長方形の和
- 部分配列のカウント — 和が k、k で割り切れる和
- 積に関する問題 — 自分以外の積
- 平衡 — ピボットインデックスの検索
- 範囲更新 — 差分配列
# Template: prefix sum + hash map for subarray problems
from collections import defaultdict
def subarray_count_template(nums, target):
"""
Count subarrays with property involving prefix sums.
Adapt 'target' and lookup condition for each problem.
"""
freq = defaultdict(int)
freq[0] = 1 # empty prefix at sum=0
current = 0
count = 0
for n in nums:
current += n
count += freq[current - target] # adjust per problem
freq[current] += 1
return count
print(subarray_count_template([1,2,3,2,1], 3)) # 3累積和と累積最大値
累積和以外にも、多くの問題では 1 つの変数で累積最大値や累積最小値を保持します。株の売買の最適なタイミング問題では価格の累積最小値を使い、左側から雨水をトラップする問題では左側の高さの累積最大値を使います。これらのパターンは 1 回の走査と O(1) の追加領域だけで処理できるため、時間と空間の両方で効率を高める模範的な方法です。
def max_profit(prices):
# Running minimum buy price
min_price = float('inf')
max_prof = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_prof:
max_prof = price - min_price
return max_prof
def left_max_array(heights):
# Running max from left for trapping rain water
n = len(heights)
left_max = [0] * n
left_max[0] = heights[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], heights[i])
return left_max
print(max_profit([7,1,5,3,6,4])) # 5理解度チェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の内容を理解できているか確認します。
レッスンのまとめ
このレッスンでは、累積和によって、累積値を 1 回の O(n) の走査で前計算し、O(n) の範囲クエリを O(1) の参照に変換できること、累積和とハッシュマップを組み合わせることで、指定した和または割り切れる性質を持つ部分配列のカウントを O(n) で解けること、そして差分配列はその逆であり、範囲更新を O(1) で行い、最後に 1 回の累積和の再構築で結果を得られることを学びました。次は、両端から向かい合うポインターを使う方法から 2 ポインターのテクニックを始めます。
AI チューターと学ぶ Python — 無料
ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。
- コース
- 30
- レッスン
- 120
よくある質問
「累積和とランニングトータル」レッスンは無料ですか？
はい。「累積和とランニングトータル」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「累積和とランニングトータル」で何を学びますか？
O(1)で区間和のクエリに答えられる累積和配列を作り、最大和部分配列などの部分配列問題に応用します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「累積和とランニングトータル」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。