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]
- 説明
- 配列全体の合計は
18、最後の2つの値の合計は1 + 8 = 9、インデックス0のみでは2、インデックス1から2までは7 + 1 = 8です。
発展問題
数値がグリッド状に並んでいて、各クエリが長方形範囲の合計を求めるものだとしたら、各クエリに定数時間で答えられるよう、累積和をどのように拡張しますか？
ヒント
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回の減算で求められます。
各範囲を合計する
正しいが、最大のテストでは終わらない
考え方
各クエリについて、nums[left] から nums[right] までを合計に加算します。範囲内のすべての値を読み取るため、これは正しい方法です。また、1つのクエリに対しては、これが可能な最善の方法です。1つのクエリの対象は最大 n 個の値に及ぶため、q 個のクエリには最大 n × q 回の加算が必要です。n = 10^4、q = 1500 の場合は 1.5 × 10^7 回となり、そのほとんどが重複します。
アルゴリズム
- 空の回答リストを作成します。
- 各クエリ
[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]の場合、[0, 3, 1, 6, 7, 3, 9]になります。
範囲[left, right]の合計は、インデックスrightまでの合計から、インデックスleftより前の合計を引いたものです。つまり、prefix[right+1] - prefix[left]です。[1, 4]の場合、prefix[5] - prefix[1] = 3 - 3 = 0です。先頭に0を置くことで、インデックス0から始まる範囲にも同じ式を使えます。n回の加算を1回行えば配列を作成でき、各クエリは1回の減算で処理できます。
アルゴリズム
- 長さが
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]の結果は1ではなく0になります。prefixをnumsと同じ長さにすること。この場合、prefix[i]にはnums[i]が含まれます。すると、0から始まる範囲ではprefix[-1]が必要になりますが、これは範囲外であり、Pythonではエラーにならずに最後の要素が読み取られます。- 総当たりループを
i < rightで止めること。両端が含まれるため、[3, 3]の合計は何も加算されません。 - 1から数え始めるLuaとRでは、0始まりのクエリ
[left, right]がnums[left+1]からnums[right+1]までを対象とし、累積和のインデックスも同じようにずれます。
よくある質問3
累積和配列とは何ですか？
各要素が、その位置より前にあるすべての値の合計である配列です。prefix[i] = nums[0] + ... + nums[i-1]で、prefix[0] = 0です。1回の走査で作成でき、その後、任意の範囲[left, right]の合計はprefix[right+1] - prefix[left]となります。
累積和を使った範囲和クエリの時間計算量はどれくらいですか？
接頭辞配列の構築に一度だけ O(n)、クエリごとに O(1) かかるため、q 個のクエリでは合計 O(n + q) です。各範囲を直接すべて加算すると、クエリごとに最大 O(n)、合計で O(n·q) かかります。
クエリの間に配列が変化する場合はどうでしょうか？
そのため、接頭辞配列は適切な方法ではありません。更新を1回行うと、それ以降のすべての合計がずれてしまい、修正に O(n) かかるからです。Fenwick tree またはセグメント木なら、更新と区間和のどちらも O(log n) で処理できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def sumRange(nums, queries):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
期待される出力
[6, 0, 1]