Namaran

Code daily. Without assist.

2026-09-04

fenwick_set.c

void fw_set(long t[], int n, int i, long v) {
}

t[1]〜t[n] は、配列 a[1]〜a[n] から作った Fenwick木です。t[k] は a[k - (k & -k) + 1]〜a[k] の和で、t[0] は使いません。元の配列 a はもう手元にありません。a[i] を v に置き換えたときの Fenwick木になるよう t を書き換える fw_set を書いてください。i は 1 以上 n 以下です。入出力例では t[1]〜t[n] を並べて示します。

入力例 1

t = {3, 4, 4, 9, 5}; fw_set(t, 5, 3, 0);

出力例 1

t = {3, 4, 0, 5, 5}

入力例 2

t = {3, 4, 4, 9, 5}; fw_set(t, 5, 1, 10);

出力例 2

t = {10, 11, 4, 16, 5}

入力例 3

t = {7}; fw_set(t, 1, 1, 2);

出力例 3

t = {2}
Reference
void fw_set(long t[], int n, int i, long v) {
    long cur = 0;
    for (int j = i; j > 0; j -= j & -j)
        cur += t[j];
    for (int j = i - 1; j > 0; j -= j & -j)
        cur -= t[j];
    for (long d = v - cur; i <= n; i += i & -i)
        t[i] += d;
}

Fenwick木に直接できるのは、a[i] に差分 d を足すことだけです。置き換えるには、いまの a[i] を知って d = v - a[i] を足します。いまの a[i] は、先頭から i 個の和と i - 1 個の和の差です。最初の2つのループは、j から j & -j を引きながら t[j] を拾い、この2つの和を求めます。最後のループは、i & -i を足しながら差分を積む、ふだんの更新です。

t[i] = v と書くと誤りになります。t[i] が持つのは a[i] だけでなく、その手前を含む区間の和です。そのうえ a[i] は、i から上に続く節にも含まれています。例1では t[4] が a[1]〜a[4] の和 9 なので、a[3] を 4 から 0 にしたら t[3] と一緒に t[4] も 4 減らす必要があります。

掲載したのは参考実装で、唯一の正解ではありません。i 個の和と i - 1 個の和は、たどる節が途中から同じになるので、そこから先は足しても引いても打ち消し合います。その手前で止めれば、ループを短くできます。元の値を別の配列に持っておけるなら、差分はその配列から求まります。