差分配列と累積和のアルゴリズム

差分配列と累積和

テンプレート（疑似コード）

// 元データの読み込み: n, m, a
n, m = 入力()
for i = 0 to n-1:
    a[i] = 入力()  // 元の配列

// 差分配列の構築
for i = 0 to n-1:
    diff[i] = a[i] - a[i-1]

// 区間操作
while m > 0:
    m = m - 1
    l, r, value = 入力()
    diff[l] = diff[l] + value
    diff[r+1] = diff[r+1] - value

// 累積和で復元
for i = 0 to n-1:
    diff[i] = diff[i] + diff[i-1]

例題：大学の木への農薬散布

問題概要

$N$本の木（番号は $0$ から $N-1$）が直線上に並んでいる。位置と树种によって異なる農薬が必要となる。

農薬は区間単位で散布され，例如ば $3$番から$5$番の木には駆虫剤，$20$番から$26$番の木には根系活性化剤など，異なる区間に異なる農薬が必要となる。

各区間に要する費用が与えられたとき，全体の散布コスト総額を求めよ。

入力形式

1行目に整数 $N$ と $M$ が空白区切りで与えられる。続く$M$行に，各区間の開始位置 $L$，終了位置 $R$，および費用 $C$ が空白区切りで与えられる。

$1 \le L \le R \le N \le 10^6$, $1 \le M \le 10^5$，費用はint範囲内

出力形式

全体の費用合計を1行で出力する。

入出力例

解法ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int treeCount, intervalCount;
    cin >> treeCount >> intervalCount;
    
    const int MAX = 1000000;
    static long long diffArr[MAX + 5];
    
    for (int i = 0; i < intervalCount; ++i) {
        int startPos, endPos, cost;
        cin >> startPos >> endPos >> cost;
        
        // 差分配列の特性を利用し，区间更新を端点操作に変換
        diffArr[startPos + 1] += cost;
        diffArr[endPos + 2] -= cost;
    }
    
    // 累積和で元の配列を復元
    for (int i = 1; i <= treeCount; ++i) {
        diffArr[i] += diffArr[i - 1];
    }
    
    long long totalCost = 0;
    for (int i = 1; i <= treeCount; ++i) {
        totalCost += diffArr[i];
    }
    
    cout << totalCost << '\n';
    return 0;
}

累積和の基本的な問題解法

// 基本手順
n, m = 入力()
accum[0] = 0

// 前計算：累積和配列の構築
for i = 1 to n:
    a = 入力()
    accum[i] = accum[i-1] + a

// 区間クエリへの応答
while m > 0:
    m = m - 1
    l, r = 入力()
    result = accum[r] - accum[l-1]
    結果を出力

例題：大学の木々のメンテナンス

問題概要

$N$本の木が直線状に排列している。各木には既に維持管理費用が記録されている。

各木마다管理費用は異なる。特定の区間内の木の管理費用の合計を求めるクエリが$M$件与えられるので，各クエリに対して答えを出力せよ。

入力形式

1行目に $N$ と $M$ が空白区切りで与えられる。2行目に$N$個の整数 $A_1, A_2, \ldots, A_N$ が空白区切りで与えられる。続く$M$行にクエリ区間の開始位置 $L$ と終了位置 $R$ が与えられる。

出力形式

各クエリに対して，区間内の管理費用合計を1行ずつ出力する。

入出力例

入力:
10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7

出力:
24
22
17

解法ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int totalElements, queryCount;
    cin >> totalElements >> queryCount;
    
    const int MAX_SIZE = 100005;
    static int elementArr[MAX_SIZE];
    static long long prefixSum[MAX_SIZE];
    
    // 累積和の前計算
    for (int i = 1; i <= totalElements; ++i) {
        cin >> elementArr[i];
        prefixSum[i] = prefixSum[i - 1] + elementArr[i];
    }
    
    // クエリの処理
    for (int q = 0; q < queryCount; ++q) {
        int leftIdx, rightIdx;
        cin >> leftIdx >> rightIdx;
        
        long long rangeSum = prefixSum[rightIdx] - prefixSum[leftIdx - 1];
        cout << rangeSum << '\n';
    }
    
    return 0;
}

アルゴリズムの解説

差分配列は，配列のある区間に対して一括で値を加减する場合に有効な手法である。区間 $[l, r]$ に値 $v$ を加算したい場合，差分配列の $l$ 位置に $v$，$r+1$ 位置に $-v$ を加算するだけでよい。最後に累積和を取ることで元の配列が復元できる。

累積和は，配列の区間和を高速に計算するための前処理手法である。$sum[i]$ を $a_1$ から $a_i$ までの合計と定義すると，任意区間 $[l, r]$ の和は $sum[r] - sum[l-1]$ で $O(1)$ 时间に求められる。

タグ: C++ アルゴリズムデータ構造差分配列累積和

5月18日 21:33 投稿

異端開発室

差分配列と累積和のアルゴリズム