Pythonで範囲合計をサポートするデータ構造を定義するプログラム

整数のリストで構築できるデータ構造を開発したいとします。効率的な方法で必要なときはいつでも、インデックスiからインデックスj-1までの要素の合計を見つける関数があります。 2つの機能があります。

• 整数配列を使用して新しいインスタンスを構築するコンストラクター。
• get_sum（i、j）は、開始インデックスiと終了インデックスj-1からの配列要素の整数の合計を返します。

したがって、入力がarray =[5,2,3,6,4,7,8,9,3,2]のような場合は、オブジェクトobjを作成し、関数obj.get_sum（1,5）およびobjを呼び出します。 get_sum（4,8）の場合、出力はそれぞれ15と28になります。最初の範囲要素は[2,3,6,4]であるため、合計は15であり、2番目の範囲要素は[4,7,8,9]であるため、ここでの合計は28です。

これを解決するには、次の手順に従います-

• コンストラクターを定義します。これには配列が必要です
• sums：=これはリストです。最初に0を挿入します
• 配列内のxごとに、
  • 合計の最後に（x +（合計の最後の項目））を挿入します
• 関数get_sum（）を定義します。これにはi、jが必要です
• return sums [j]-sums [i]

例

理解を深めるために、次の実装を見てみましょう-

class RangeSum:
   def __init__(self, array):
      self.sums = [0]
      for x in array:
         self.sums.append(x + self.sums[-1])
   def get_sum(self, i, j):
      return self.sums[j] - self.sums[i]

array = [5,2,3,6,4,7,8,9,3,2]
obj = RangeSum(array)
print(obj.get_sum(1,5))
print(obj.get_sum(4,8))

入力

[5,2,3,6,4,7,8,9,3,2]
obj.get_sum(1,5)
obj.get_sum(4,8)

出力

15
28