Namaran

Code daily. Without assist.

2026-09-04

fenwick.c

#include <stdio.h>

int t[9];

void add(int i, int v) {
    for (; i <= 8; i += i & -i)
        t[i] += v;
}

int main(void) {
    for (int i = 1; i <= 8; i++)
        add(i, i);
    printf("%d %d %d %d\n", t[4], t[6], t[7], t[8]);
}

これは何を出力するでしょうか?

Answer

10 11 7 36 です。

add は t[i] に v を足したあと、i に i & -i を足して次のマスへ進みます。C23 の符号付き整数は2の補数で表されるので、i & -i は i の一番下にある 1 のビットだけを残した値です。4 (100) なら 4、6 (110) なら 2、7 (111) なら 1 になります。

そのため add(i, i) が値 i を書き込む先は t[i] だけではありません。add(3, 3) なら t[3] に足したあと 3 + 1 = 4 へ、4 + 4 = 8 へと進み、t[3]・t[4]・t[8] の3か所に 3 を足します。t[i] には i だけが入ると読むと 4 6 7 8 と答えてしまいますが、t[k] に入るのは、進んだ先で k を通る i の合計です。

t[4] を通るのは 1 → 2 → 4、2 → 4、3 → 4、4 の4本で、1 + 2 + 3 + 4 = 10 です。t[6] を通るのは 5 → 6 と 6 で 11、t[7] は 7 から次が 8 に飛ぶので 7 だけです。どの i も最後は 8 を通るので、t[8] は 1〜8 の和 36 になります。