Namaran

Code daily. Without assist.

2026-09-23

imos_add.c

#include <stddef.h>

void imos_add(int *diff, size_t l, size_t r, int v) {
}

いもす法で使う差分配列diff(長さn + 1)に対し、半開区間[l, r)(0 <= l <= r <= n)の各要素へvを加算する効果を持たせる関数imos_addを書いてください。実際にその区間を1つずつ加算するのではなく、diffのうち2箇所だけを更新します。l == r(空区間)のときも、正味の効果はゼロのままであるべきです。diff = {0,0,0,0,0,0}にimos_add(diff, 1, 4, 3) → diff = {0,3,0,0,-3,0}、続けて同じdiffにimos_add(diff, 0, 2, 2) → diff = {2,3,-2,0,-3,0}、diff = {0,0,0,0,0,0}にimos_add(diff, 3, 3, 5) → diff = {0,0,0,0,0,0}(境界: 空区間)

Reference
void imos_add(int *diff, size_t l, size_t r, int v) {
    diff[l] += v;
    diff[r] -= v;
}

区間[l, r)の全要素へ+vする効果は、diff[l]に+v、diff[r]に-vを置くだけで表現できます。あとで先頭から累積和を取ると、diff[l]以降でその+vが効き始め、diff[r]のところでちょうど打ち消されて区間の外には影響が及びません。l == rのときは、diff[l] += v;のすぐあとに同じ位置へdiff[l] -= v;することになるので、正味の効果はゼロのままです——特別な分岐を書かなくても、境界条件(空区間)を自然に満たします。これは参考実装であり、唯一の正解ではありません。