Fenwick Ağacı

Fenvik ağacı — prefiks cəmlərini səmərəli şəkildə hesablamağa imkan verən bir məlumat strukturudur.

Bir $t$ ədədi üçün $h(t)$ $t$-nin 2^k-yə bölündüyü ən böyük $k$ ədədi olsun. Məsələn, h(24) = 3, h(5) = 0. Qoy l(t) = 2^{h(t)}; məsələn, l(24) = 8, l(5) = 1.

a_1, a_2, \ldots, a_n tam ədədlərdən ibarət bir sıra nəzərdən keçirək. Bu sıra üçün Fenvik ağacı b_1, b_2, \ldots, b_n sırasıdır ki,

Beləliklə:

- b_1 = a_1 - b_2 = a_1 + a_2 - b_3 = a_3 - b_4 = a_1 + a_2 + a_3 + a_4 - b_5 = a_5 - b_6 = a_5 + a_6 - $\dots$

Məsələn, a = (3, -1, 4, 1, -5, 9) sırası üçün Fenvik ağacı

b = (3, 2, 4, 7, -5, 4) sırasıdır.

Bir sıranı öz-Fenvik adlandıracağıq, əgər o, Fenvik ağacı ilə üst-üstə düşərsə. Məsələn, yuxarıdakı sıra öz-Fenvik deyil, amma a = (0, -1, 1, 1, 0, 9) sırası belədir.

$a$ sırası verilib. Bəzi elementlərin dəyərlərini dəyişərək və onların sırasını dəyişmədən, yeni a' sırasının öz-Fenvik olması tələb olunur. Mümkün qədər az sayda elementi dəyişərək verilmiş problemi həll edin.