範囲の合計クエリ」の問題の解決方法

単純な方法: 配列内の範囲の要素を順番に足し合わせる方法です。これは直感的で簡単ですが、配列の長さや範囲の大きさに比例して効率が低下します。

def range_sum_query_simple(arr, start, end):
   total = 0
   for i in range(start, end + 1):
       total += arr[i]
   return total

累積和を利用する方法: 配列の要素の累積和を事前に計算し、範囲の合計を高速に求める方法です。累積和は一度計算すれば再利用できるため、範囲の合計を求めるクエリに対しては効率的です。

def range_sum_query_cumulative(arr, start, end):
   cumulative_sum = [0] * (len(arr) + 1)
   for i in range(1, len(arr) + 1):
       cumulative_sum[i] = cumulative_sum[i - 1] + arr[i - 1]
   return cumulative_sum[end + 1] - cumulative_sum[start]

セグメント木を利用する方法: セグメント木は、配列の要素を効率的に管理するデータ構造です。セグメント木を構築することで、範囲の合計を高速に求めることができます。セグメント木の構築には時間がかかりますが、一度構築すれば複数の範囲の合計を高速に求めることができます。

class SegmentTree:
   def __init__(self, arr):
       self.arr = arr
       self.tree = [0] * (4 * len(arr))
       self.build(1, 0, len(arr) - 1)

   def build(self, node, start, end):
       if start == end:
           self.tree[node] = self.arr[start]
       else:
           mid = (start + end) // 2
           self.build(2 * node, start, mid)
           self.build(2 * node + 1, mid + 1, end)
           self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

   def range_sum_query(self, node, start, end, left, right):
       if start > right or end < left:
           return 0
       if start >= left and end <= right:
           return self.tree[node]
       mid = (start + end) // 2
       return self.range_sum_query(2 * node, start, mid, left, right) + self.range_sum_query(2 * node + 1, mid + 1, end, left, right)