Namaran

Code daily. Without assist.

2026-09-23

range_add_trace.c

#include <stdio.h>

int main(void) {
    int n = 5;
    int diff[6] = {0};

    diff[1] += 3; diff[4] -= 3;
    diff[0] += 2; diff[2] -= 2;
    diff[3] += -1; diff[5] -= -1;

    int prev = 0;
    for (int i = 0; i < n; i++) {
        prev += diff[i];
        printf(i ? " %d" : "%d", prev);
    }
    printf("\n");
}

このプログラムを実行すると、何が出力されるでしょうか?

Answer

2 5 3 2 -1(その後に改行)です。これは「いもす法」と呼ばれるテクニックで、区間[l, r)の各要素へ値vを足す操作を、配列diffの2箇所diff[l] += v; diff[r] -= v;を更新するだけで済ませ、最後に1回だけ先頭から累積和を取ることで実際の配列を復元します。区間ごとに全要素を書き換える素朴な方法だとクエリ数をQとしてO(Q * n)かかりますが、いもす法なら更新は毎回O(1)、最後の復元がO(n)で済み、合計O(Q + n)になります。このコードは3回の区間加算——[1,4)へ+3、[0,2)へ+2、[3,5)へ-1——をdiffに記録してから、prevにdiff[i]を足し込みながら累積和を取っています。実際に区間を1つずつ加算して確かめると、初期状態[0,0,0,0,0]に[1,4)へ+3で[0,3,3,3,0]、続けて[0,2)へ+2で[2,5,3,3,0]、最後に[3,5)へ-1で[2,5,3,2,-1]となり、diffからの復元結果と一致します。diffの長さがnではなくn + 1(ここでは6)であることにも意味があります——区間の右端がちょうど配列の末尾nに達するクエリでもdiff[n]へ安全に書き込めるようにするためです。