【Python】特定の範囲の要素をまとめて更新するプログラムの書き方

数値のリスト nums と操作のリスト operations が与えられているとします。各操作は [L, R, X] という3つのフィールドを持ち、「インデックス L から R まで（両端を含む）のすべての要素に X を加算する」という意味です。すべての操作を適用し、最終的なリストを返すのがこの問題の目的です。

問題の例

たとえば、入力が次のような場合を考えてみましょう。

nums = [8, 4, 2, -9, 4]
operations = [[0, 0, 3], [1, 3, 2], [2, 3, 5]]

このときの出力は [11, 6, 9, -2, 4] になります。初期リストが [8, 4, 2, -9, 4] であり、各操作が以下のように段階的に適用されるためです。

• 最初の操作 [0, 0, 3] を実行 → リストは [11, 4, 2, -9, 4] になる
• 次の操作 [1, 3, 2] を実行 → リストは [11, 6, 4, -7, 4] になる
• 最後の操作 [2, 3, 5] を実行 → リストは [11, 6, 9, -2, 4] になる

解法のアプローチ：イベント方式（差分記録）

各操作のたびに範囲内の要素を直接書き換えると、操作数や範囲の長さが大きくなった際に計算量が膨張してしまいます。そこで有効なのが「イベント方式」と呼ばれる手法です。区間の始点で加算イベントを、終点+1の位置で減算イベントを記録しておき、あとから先頭から一括して累積することで、範囲更新を効率的に処理できます。

具体的な手順は以下の通りです。

• events := 新しい空のリストを作成する
• operations 内の各 (l, r, inc) について：
  • events の末尾に (l, inc) を追加する
  • events の末尾に (r + 1, -inc) を追加する
• events リストをソートする
• inc := 0、ptr := 0 と初期化する
• i を 0 から nums のサイズ未満まで繰り返す：
  • ptr < len(events) かつ events[ptr][0] == i の間、次を繰り返す：
    • inc := inc + events[ptr][1]
    • ptr := ptr + 1
  • nums[i] := nums[i] + inc
• nums を返す

この方法のポイントは、各位置における「現在の累積加算値」を変数 inc で管理しながら、配列を一度だけ走査する点にあります。区間の開始位置で値を増やし、終了位置の直後で減らすことで、どの要素にいくつ加算すべきかを正確に把握できる仕組みです。

Python実装例

理解を深めるために、実際のコードを見てみましょう。

class Solution:
   def solve(self, nums, operations):
      events = []
      for l, r, inc in operations:
         events.append((l, inc))
         events.append((r + 1, -inc))
      events.sort()
      inc = 0
      ptr = 0
      for i in range(len(nums)):
         while ptr < len(events) and events[ptr][0] == i:
            inc += events[ptr][1]
            ptr += 1
         nums[i] += inc
      return nums
ob = Solution()
nums = [8, 4, 2, -9, 4]
operations = [ [0, 0, 3], [1, 3, 2], [2, 3, 5] ]
print(ob.solve(nums, operations))

入力

nums = [8, 4, 2, -9, 4]
operations = [[0, 0, 3], [1, 3, 2], [2, 3, 5]]

出力

[11, 6, 9, -2, 4]

計算量について

N を配列の要素数、M を操作の数とすると、このアルゴリズムの時間計算量は O(M log M + N) です。イベントリストのソートが支配的であり、その後の走査は線形時間で完了します。各操作を素朴に適用する方法（最悪 O(N × M)）と比べ、大量のデータでも高速に動作する点が大きなメリットです。