Namaran

Code daily. Without assist.

2026-09-23

imos_bounds.c

#include <stdio.h>

int main(void) {
    int n = 5;
    int diff[5] = {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");
}

いもす法で複数の区間加算をまとめて処理し、最終的な配列を求めるつもりのプログラムです。適用しているクエリは[1,4)へ+3、[0,2)へ+2、[3,5)へ-1(n=5)。配列の境界を超えて書き込むため、いまの出力は保証されません(このコードは実際にクラッシュすることがあります)。本来の出力は2 5 3 2 -1です。何が問題で、どう直せばよいでしょうか?

Answer

差分配列diffは、区間の右端rが配列の末尾n(ここでは5)に達するクエリのために、要素数をnではなくn + 1だけ確保しておく必要があります。ここでは[3,5)への加算の打ち消しとしてdiff[5] -= -1;を書き込んでいますが、diffはint diff[5]、つまり添字0から4までしか確保されていないため、diff[5]への書き込みは配列の境界を超えています。境界外への書き込みは未定義動作であり、この場合はスタック上の配列のすぐ外を書き換えてしまうため、実行結果が不定になったりクラッシュしたりします。直し方は、diffのサイズをn + 1(ここでは6)に直すだけです:

int diff[6] = {0};