De ce contează?
Imaginează-ți un raft cu borcane numerotate. Borcanul de la poziția i nu ține
suma unui singur element, ci suma unui întreg bloc care se termină la i — iar
mărimea blocului e dată de ultimul bit aprins din numărul i. Ca să afli
suma primelor 6 elemente nu deschizi 6 borcane, ci doar câteva: combini borcanul
care acoperă pozițiile 5–6 cu cel care acoperă 1–4. Asta e un Fenwick Tree.
Intuiția
Vrei două lucruri pe un șir: suma unui prefix și modificarea unui element,
amândouă rapid. Un Fenwick (arbore indexat binar) ține un singur vector bit[]
în care fiecare poziție memorează suma unui bloc. Ascunsă în reprezentarea binară
a indexului stă o regulă elegantă: blocul de la i are exact i & -i elemente.
bit[i] răspunde de exact ultimele i & -i poziții care se termină la i —
atâtea câte spune ultimul bit aprins al lui i. De aceea orice prefix se sparge
în O(log n) blocuri: scrii indexul în binar și fiecare bit aprins devine un bloc.
De exemplu 6 = 110 = 4 + 2, deci prefixul 1..6 = blocul 1–4 (de mărime 4)
plus blocul 5–6 (de mărime 2). Descompunerea binară a lui i este lista de borcane.