2026-09-04
prefix_sum.c
#include <stdio.h>
int t[5];
int sum(int i) {
int s = 0;
for (; i > 0; i -= i & -i)
s += t[i];
return s;
}
int main(void) {
int a[4] = {5, 3, 7, 9};
for (int i = 0; i < 4; i++)
for (int j = i; j <= 4; j += j & -j)
t[j] += a[i];
printf("%d\n", sum(3));
}
main は配列 a を Fenwick木 t に積み、sum(3) で a の先頭3個の和を出力するつもりのプログラムです。本来は 5 + 3 + 7 の 15 を出力するはずですが、いまは何も出力しないまま終わりません。
Answer
Wrong
for (int i = 0; i < 4; i++)
for (int j = i; j <= 4; j += j & -j)
t[j] += a[i];
最初の i = 0 で内側のループから抜け出せません。内側のループは j に j & -j を足して次の節へ進みますが、0 & -0 は 0 なので、j は 0 のまま動きません。j <= 4 はいつまでも真のままで、t[0] に 5 を足し続けます1。
j & -j は j の一番下にある 1 のビットです。1 以上の j なら必ず 1 以上になり、ループは毎回先へ進みます。立っているビットが1つもないのは 0 だけで、Fenwick木が位置を 1 から数えるのはこのためです。
Right
for (int i = 0; i < 4; i++)
for (int j = i + 1; j <= 4; j += j & -j)
t[j] += a[i];
配列の a[i] を、木の位置 i + 1 に対応させます。位置は 1〜4 になり、どれも更新のループが先へ進みます。sum(3) は位置 1〜3 に入った a[0]〜a[2] の和 5 + 3 + 7 = 15 を返します。
t[0]はintなので、足し続けるといずれINT_MAXを超えます。符号付き整数のオーバーフローは未定義動作なので、最適化の具合によっては、止まらない以外の振る舞いになることもあります。