差分配列は、配列の特定区間に対して効率的に値を加算・減算するための手法です。通常の配列操作では、ある区間に対して変更を加える場合、直接その区間すべての要素を更新する必要がありますが、差分配列を使うとこの更新処理を2回の操作で完了させることができます。

1. 差分配列は、ある要素がその次の要素とどれだけ変化したかを記録する配列です。
2. 差分配列を操作し、最終的に累積和を計算することで元の配列を構築します。

• 元の配列を arr とします。
• 差分配列を diff とします。

[ diff[i] = arr[i] - arr[i-1] \quad (i \geq 1) ]

[ arr[i] = \text{累積和} \quad \sum_{j=1}^{i} diff[j] ]

長さ ( N ) の配列に対して、以下のような操作を効率的に行いたい：

• 区間 [L, R] に値 ( x ) を加算する。

通常の配列では、区間 [L, R] の各要素を直接更新します：

for i in range(L, R + 1):
    arr[i] += x

この方法では、更新に ( O(R-L+1) ) の時間がかかります。

差分配列では、区間操作を次のようにします：

1. diff[L] += x （区間の始点に ( x ) を加算）
2. diff[R+1] -= x （区間の終点の次の位置に ( -x ) を加算）

この更新では、2回の操作で完了します。

差分配列の累積和を計算することで元の配列を復元します： [ arr[i] = \sum_{j=1}^{i} diff[j] ]

長さ 10 の配列を初期化し、次の操作を行った後、配列の状態を求めなさい。

1. 区間 [2, 5] に 3 を加算。
2. 区間 [4, 8] に 2 を加算。
3. 区間 [1, 10] に 1 を加算。

1. 初期化:

   • 配列の長さは 10。差分配列 diff を 0 で初期化します。

     diff = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     

2. 操作 1: [2, 5] に 3 を加算:

   • diff[2] += 3
   • diff[6] -= 3

     diff = [0, 0, 3, 0, 0, 0, -3, 0, 0, 0, 0]
     

3. 操作 2: [4, 8] に 2 を加算:

   • diff[4] += 2
   • diff[9] -= 2

     diff = [0, 0, 3, 0, 2, 0, -3, 0, 0, -2, 0]
     

4. 操作 3: [1, 10] に 1 を加算:

   • diff[1] += 1
   • diff[11] -= 1（11 番目は配列外なので無視）

     diff = [0, 1, 3, 0, 2, 0, -3, 0, 0, -2, 0]
     

5. 累積和を計算して元の配列を復元:

   arr = [0] * 10
   current = 0
   for i in range(1, 11):
       current += diff[i]
       arr[i-1] = current

   • 計算結果:

     arr = [1, 4, 4, 6, 6, 3, 3, 3, 1, 1]
     

1. 高速な区間操作:

   • 通常の操作は ( O(R-L+1) ) ですが、差分配列では ( O(1) ) で更新可能です。
   • 累積和計算は ( O(N) ) の計算量。

2. メモリ効率:

   • 元の配列と同じ長さの差分配列を利用。

3. 制約が大きい場合でも対応可能:

   • ( N ) や ( Q ) が大きい場合に非常に有効。

1. 区間加算・減算が多い問題。
2. 大規模データ（長さ ( N ) が ( 10^5 ) 以上）での効率的な操作が求められる場合。
3. 範囲指定された変更の影響を効率的に追跡する必要がある場合。