Range Sum Query
変更されない整数の配列 nums と、queries のリストが与えられます。各クエリは0始まりのインデックスのペア [left, right] で、両端を含む nums[left] + nums[left+1] + ... + nums[right] の値を求めます。クエリと同じ順序で答えを返してください。
関数
- numsinteger-array
- 整数の配列。すべてのクエリで同じ
- queriesinteger-2d-array
- 合計する範囲。それぞれは left ≤ right を満たすペア [left, right] です。
- 戻り値integer-array
- 各クエリについて、クエリの順に各範囲の合計
制約
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthすべてのクエリ[left, right]について
例
- 入力
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- 出力
- [6, 0, 1]
- 説明
- インデックス0から2には
3 + (-2) + 5 = 6が格納されています。インデックス1から4には-2 + 5 + 1 + (-4) = 0が格納されています。範囲[3, 3]は単一の値1です。
- 入力
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- 出力
- [18, 9, 2, 8]
- 説明
- 配列全体の合計は
2 + 7 + 1 + 8 = 18、最後の2つの値の合計は1 + 8 = 9、インデックス0だけでは2、インデックス1から2までは7 + 1 = 8です。
提出時に隠しテスト+14件
発展問題
これで数値はグリッド状に並び、各クエリでは2つの角で指定された長方形の合計を求めます。各クエリに定数回の演算で答えられるように、累積和をどのように拡張しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
多くのクエリは、ほぼ同じ値を対象としています。クエリを読む前に、一度だけ行える作業は何でしょうか？
すべての
iについて最初のi個の値の合計がわかっていれば、範囲の合計はそのような合計の2つの差になります。prefixを、prefix[0] = 0およびprefix[i+1] = prefix[i] + nums[i]で構築します。すると、各クエリ[left, right]はprefix[right+1] - prefix[left]となります。
解説
1つの範囲はループです。問題はその数です。各クエリは配列の大部分を対象にする可能性があるため、1つずつ個別に合計すると、同じ加算を何度も繰り返すことになります。すべてを一度だけ累積和に加算すれば、各範囲は1回の減算で求められます。
各範囲を合計する
正しいが、最大のテストでは終わらない
考え方
各クエリは個別に答えます。合計を 0 で始め、nums[left] から nums[right] までを加算して、結果を保存します。[3, -2, 5, 1, -4, 6] の [1, 4] の場合は、-2 + 5 + 1 + (-4) = 0 です。
これは正しい方法であり、クエリが 1 つだけなら最善の方法です。範囲内の各値を一度ずつ読み取る必要があるからです。コストは繰り返しにあります。クエリは最大で n 個の値にまたがるため、q 個のクエリには最大で n × q 回の加算が必要です。n = 10^4 で、配列の大部分をそれぞれカバーするクエリが 1500 個ある場合、加算は約 1.3 × 10^7 回となり、そのほとんどは前のクエリで行った作業の繰り返しです。
答えのリストに加えて合計を 1 つ保持するため、追加の空間は O(1) です。
アルゴリズム
- 空の回答リストを作成します。
- 各クエリ
[left, right]について、total = 0を設定します。 leftからrightまで（両端を含む）の各iについて、nums[i]をtotalに加算します。totalを回答リストに追加し、最後のクエリの後に回答リストを返します。
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answers累積和
考え方
prefix[i]を最初のi個の値の合計とします。空の先頭部分に対してはprefix[0] = 0です。[3, -2, 5, 1, -4, 6]の場合、prefix = [0, 3, 1, 6, 7, 3, 9]となります。各要素はその直前の要素に値を1つ加えたものなので、配列全体の計算にはn回の加算が必要です。
範囲[left, right]の合計は、インデックスrightまで（インデックスrightを含む）の合計から、インデックスleftより前の合計を引いたものです。つまりprefix[right+1] - prefix[left]です。[1, 4]の場合は、prefix[5] - prefix[1] = 3 - 3 = 0です。[0, 2]の場合は、prefix[3] - prefix[0] = 6 - 0 = 6です。先頭の0があることで、インデックス0から始まる範囲も特別な処理なしで扱えます。
配列の構築にはO(n)かかり、その後の各クエリは減算1回で済むため、合計の時間計算量はO(n + q)、追加の空間計算量はO(n)です。ここでの累積和はどれも10^4 × 10^4 = 10^8を超えないため、32ビット整数で十分です。
アルゴリズム
- 長さが
n+1のprefixを作成し、prefix[0] = 0とします。 0からn-1までの各iについて、prefix[i+1] = prefix[i] + nums[i]を設定します。- 各クエリ
[left, right]について、prefix[right+1] - prefix[left]を答えに追加します。 - 答えを返します。
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
落とし穴と境界ケース
ここでのバグは、ほとんどすべてがインデックスのずれです。
prefix[right] - prefix[left]と書いてしまう。prefix[0] = 0の場合、nums[right]が除外されるため、範囲[3, 3]の結果は、インデックス3の値ではなく0になります。prefixをnumsと同じ長さで作り、prefix[i]にnums[i]を含めてしまう。その場合、0から始まる範囲ではprefix[left-1]が必要になりますが、これは範囲外であり、Pythonではエラーにならず最後の要素を読み取ります。先頭に余分な0を置けば、この特別なケースをなくせます。- 総当たり処理を
i < rightで終了してしまう。範囲の両端はどちらも含まれます。 - LuaとRでは1から数えることを忘れてしまう。ここでは、0始まりのクエリ
[left, right]はnums[left+1]からnums[right+1]までを対象とし、累積和の差も同様にずれます。 - 値や長さが大きくなる場合に、32ビットの合計値を使ってしまう。ここでの最大の合計は
10^8ですが、値が10^9近くになると累積和はすぐにオーバーフローするため、64ビット配列を使うのが安全です。
よくある質問4
累積和配列とは何ですか？
各要素が、その位置より前にあるすべての値の合計となる配列です。prefix[i] = nums[0] + ... + nums[i-1]で、prefix[0] = 0です。これを1回の走査で作成すると、その後は任意の範囲[left, right]の合計を、1回の引き算prefix[right+1] - prefix[left]で求められます。
累積和を使った区間和クエリの時間計算量はどのくらいですか？
接頭辞配列を一度構築するのに O(n)、クエリごとに O(1) なので、q 個のクエリでは O(n + q) です。各範囲を直接すべて足し合わせると、クエリごとに最大 O(n) かかり、合計では O(n·q) になります。
prefix 配列の要素数が nums より 1 つ多いのはなぜですか？
追加の prefix[0] = 0 は、配列の空の開始位置を表します。これにより、インデックス 0 から始まる範囲も含め、すべての範囲で同じ式を使えます: prefix[right+1] - prefix[0]。これがない場合は、left = 0 用に個別の分岐が必要です。
クエリの間に配列が変化する場合はどうなるでしょうか？
その場合、更新のたびに後続のすべての合計値がずれ、修正にO(n)かかるため、累積和配列は適切な手段ではありません。Fenwick treeまたはセグメントツリーなら、更新と区間和の計算の両方をO(log n)で処理できます。配列が変化しない場合は、通常の累積和のほうが高速で簡潔です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def sumRange(nums, queries):
# ここにコードを書いてくださいケース1
ケース2
入力
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
期待値
[6, 0, 1]