Namaran

Code daily. Without assist.

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 を返します。

  1. t[0] は int なので、足し続けるといずれ INT_MAX を超えます。符号付き整数のオーバーフローは未定義動作なので、最適化の具合によっては、止まらない以外の振る舞いになることもあります。