累積和・差分配列

前処理による配列の区間操作を劇的に高速化する重要な技法を学ぼう

O(1)

クエリ時間

O(n)

前処理時間

初中級

難易度

その他

カテゴリ

🔧 実行設定

操作:

build

配列:

[1, 3, 5, 7, 9, 11, 13, 15]

配列（カンマ区切り）

左端 (L)

右端 (R)

値（更新用）

💡 推奨操作

📊

アルゴリズムを実行してください

左側の設定パネルから操作を選択し、「アルゴリズム実行」ボタンを押してください

💻 実装例（JavaScript）

// 累積和の構築
function buildCumulativeSum(arr) {
    const n = arr.length;
    const cumSum = new Array(n + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        cumSum[i + 1] = cumSum[i] + arr[i];
    }
    
    return cumSum;
}

// 区間和クエリ O(1)
function rangeSum(cumSum, left, right) {
    return cumSum[right + 1] - cumSum[left];
}

// 差分配列による区間更新 O(1)
function rangeUpdate(diff, left, right, value) {
    diff[left] += value;
    if (right + 1 < diff.length) {
        diff[right + 1] -= value;
    }
}

// 差分配列から元配列を復元 O(n)
function restore(diff) {
    const n = diff.length;
    const arr = new Array(n);
    arr[0] = diff[0];
    
    for (let i = 1; i < n; i++) {
        arr[i] = arr[i - 1] + diff[i];
    }
    
    return arr;
}

// 使用例
const arr = [1, 3, 5, 7, 9];
const cumSum = buildCumulativeSum(arr);
console.log(rangeSum(cumSum, 1, 3)); // 15 (3+5+7)

🔧 実行設定

💡 推奨操作

アルゴリズムを実行してください

累積和・差分配列とは？

💻 実装例（JavaScript）