プレフィックス和アルゴリズム

基本概念

プレフィックス和は配列処理技術の一種で、事前計算により部分区間の和をO(1)で取得可能にします。入力配列をdataとすると、プレフィックス配列prefは次のように定義されます：

pref[i] = data[0] + data[1] + ... + data[i]
pref[0] = data[0]

構築方法

C++による実装例：

vector<int> constructPrefixArray(const vector<int>& nums) {
    vector<int> pref(nums.size());
    pref[0] = nums[0];
    for (size_t idx = 1; idx < nums.size(); ++idx) {
        pref[idx] = pref[idx-1] + nums[idx];
    }
    return pref;
}

応用例

区間[L,R]の和計算：

int getRangeSum(const vector<int>& pref, int L, int R) {
    return (L == 0) ? pref[R] : pref[R] - pref[L-1];
}

二次元拡張

vector<vector<int>> build2DPrefix(const vector<vector<int>>& mat) {
    int rows = mat.size(), cols = mat[0].size();
    vector<vector<int>> pref(rows, vector<int>(cols));
    
    pref[0][0] = mat[0][0];
    for (int c = 1; c < cols; ++c) 
        pref[0][c] = pref[0][c-1] + mat[0][c];
    
    for (int r = 1; r < rows; ++r) 
        pref[r][0] = pref[r-1][0] + mat[r][0];
    
    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            pref[r][c] = pref[r-1][c] + pref[r][c-1] 
                       - pref[r-1][c-1] + mat[r][c];
        }
    }
    return pref;
}

差分アルゴリズム

基本概念

差分はプレフィックス和の逆操作で、区間更新を効率化します。元配列originalに対し、差分配列diffは：

diff[0] = original[0]
diff[i] = original[i] - original[i-1] (i > 0)

構築方法

vector<int> createDiffArray(const vector<int>& original) {
    vector<int> diff(original.size());
    diff[0] = original[0];
    for (size_t i = 1; i < original.size(); ++i) {
        diff[i] = original[i] - original[i-1];
    }
    return diff;
}

区間更新

void addToRange(vector<int>& diff, int L, int R, int value) {
    diff[L] += value;
    if (static_cast<size_t>(R+1) < diff.size()) {
        diff[R+1] -= value;
    }
}

配列復元

vector<int> restoreArray(const vector<int>& diff) {
    vector<int> result(diff.size());
    result[0] = diff[0];
    for (size_t j = 1; j < diff.size(); ++j) {
        result[j] = result[j-1] + diff[j];
    }
    return result;
}

二次元差分

void update2DRange(vector<vector<int>>& diff, 
                  int x1, int y1, int x2, int y2, int val) {
    diff[x1][y1] += val;
    if (x2+1 < diff.size()) diff[x2+1][y1] -= val;
    if (y2+1 < diff[0].size()) diff[x1][y2+1] -= val;
    if (x2+1 < diff.size() && y2+1 < diff[0].size()) 
        diff[x2+1][y2+1] += val;
}

応用パターン

区間更新＋単点取得：差分配列で更新後、プレフィックス和で復元
区間更新＋区間取得：高度なデータ構造と組み合わせて実現

性能比較

利用指針

• クエリ中心処理 → プレフィックス和
• 更新中心処理 → 差分
• 多次元データ → 二次元拡張版適用