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};