💡imos法（区間への足し算）

今回は paiza の「区間への足し算」の問題に挑戦！

新たに「imos法」を学んだ！

問題概要

問題の内容

• 長さ N の数列 A が与えられる
• 続いて M 個のクエリが与えられる
• 各クエリは
  「指定された区間のすべての要素に同じ値を足す」 という操作

各クエリの意味

• クエリ (l_i, u_i, a_i) について
  要素番号が l_i 以上 u_i 以下 のすべての要素に a_i を加算する

処理の流れ

• すべてのクエリを 順番に実行する
• クエリの途中で出力はしない
• 全クエリ処理後の最終的な数列 A を求める

入力の構成

• 1行目：
  • N（数列の長さ）
  • M（クエリの数）
• 2行目：
  • 初期状態の数列 A_1, A_2, ..., A_N
• 3行目以降：
  • 各クエリ (l_i, u_i, a_i)

出力の内容

• クエリ処理後の数列 A を 1要素ずつ、N 行で出力

入力例:

10 5
1 2 3 4 5 6 7 8 9 10
1 6 10
8 10 5
2 8 3
3 7 -5
3 6 1

出力例:

11
15
12
13
14
15
5
16
14
15

△NG？例：TLEの可能性

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', (inputLine) => lines.push(inputLine));

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const arrA = lines[1].split(' ').map(Number);
    const query = lines.slice(2).map(line => line.split(' ').map(Number));
    
    const prefixSum = Array(N).fill(0);
    for (let i = 0; i < N; i++) {
        prefixSum[i + 1] = prefixSum[i] + arrA[i];
    }
    
    for (let i = 0; i < M; i++) {
        const [l, u, a] = query[i];
        for (let j = l - 1; j < u; j++) {
            arrA[j] += a;
        }
    }
    
    arrA.forEach(a => console.log(a));
});

全てのクエリを問題文の通り処理すると、計算量が O(N^2) となってしまい、TLEの可能性がある(´;ω;｀)

✅Ok例：imos法

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', (inputLine) => lines.push(inputLine));

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const arrA = lines[1].split(' ').map(Number);
    const query = lines.slice(2).map(line => line.split(' ').map(Number));
    
    // 差分配列（imos法）
    const add = Array(N + 1).fill(0);

    // クエリ
    for (let i = 0; i < M; i++) {
        const [l, u, a] = query[i];
        add[l - 1] += a; // l-1 から a の加算を開始（1-index → 0-index）
        add[u] -= a; // u 以降の a の加算を打ち消す
    }

    // 加算して出力
    let current = 0; // 現在の位置(index)の要素に加算する値
    for (let i = 0; i < N; i++) {
        current += add[i];
        console.log(arrA[i] + current);　// その位置にかかるすべてのクエリの加算結果
    }
});

🔍 コードの流れ

• 入力をすべて lines 配列に読み込む
• 1行目から N（配列長）と M（クエリ数）を取得
• 2行目から元の数列 arrA を取得
• クエリ処理用に差分配列 add（長さ N+1）を用意
• 各クエリ (l, u, a) について
  • add[l-1] += a で加算開始位置を記録
  • add[u] -= a で加算終了（打ち消し）位置を記録
• add を順に累積していき、各位置で適用される加算量 current を更新
• 各位置で arrA[i] + current を計算して出力

📝まとめ

• 問題は 「区間に同じ値を何度も足す」クエリが大量にある 形式
• クエリごとに区間をループして加算すると
  → 計算量が O(N×M) ≒ O(N²) となり TLE する
• このような 区間更新問題 では、愚直実装は使えない

💡imos法

• 「毎回足す」のではなく、
  「どこから足し始め、どこで足すのをやめるか」だけを記録する
• クエリ用に 差分配列 add を用意する
• 区間 [l, u] に a を足す場合
  • add[l-1] += a（加算開始）
  • add[u] -= a（u 以降で加算を打ち消す）
    • → current 更新の累積時に打ち消される
• この時点の add は 累積和ではなく差分配列

最終結果の求め方

• add を 先頭(index=0) から順に累積していく→current
• 累積した値 → その位置に有効な全クエリの加算量
• 元の配列 A[i] にその累積値を足して出力する