Exercises — Fenwick tree (Binary Indexed Tree) — prefix sums, O(log n) update and query

$\text{lowbit}(i)$ is the largest power of two dividing $i$ — the value of the rightmost $1$ bit.

$\text{lowbit}(6)=2$, so $\text{tree}[6]$ covers the block ending at $6$ of length $2$: indices $[5,6]$. $\text{tree}[6]=a_5+a_6=5+4===9==.$

The chain of cells containing index $j$ is $j,j+\text{lowbit}(j),\dots$ up to $n$ (the update path). Start $j=5$ ($0101_2$), $\text{lowbit}=1$ → next $5+1=6$. At $6$ ($0110_2$), $\text{lowbit}=2$ → next $6+2=8$. At $8$ ($1000_2$), $\text{lowbit}=8$ → next $8+8=16>8$ stop. So the cells are $\{5,6,8\}$. True.

$7=0111_2$. Query moves down by stripping the lowest bit: $7\stackrel{-1}{\to }6\stackrel{-2}{\to }4\stackrel{-4}{\to }0.$ Cells added: $\text{tree}[7]+\text{tree}[6]+\text{tree}[4]$.

• $\text{tree}[7]$ covers $[7,7]$: $a_7=-3$.
• $\text{tree}[6]$ covers $[5,6]$: $5+4=9$.
• $\text{tree}[4]$ covers $[1,4]$: $3+2-1+6=10$. $\text{prefix}(7)=-3+9+10===16==.$ Direct check: $3+2-1+6+5+4-3=16$. ✓

$j=5$ ($0101_2$). Update moves up by adding lowbit: $5\stackrel{+1}{\to }6\stackrel{+2}{\to }8\stackrel{+8}{\to }16>8\text{stop}.$ Cells touched: $\text{tree}[5],\text{tree}[6],\text{tree}[8]$ — each gets $+4$. These are exactly the cells whose blocks contain index $5$: $[5,5]$, $[5,6]$, $[1,8]$.

$[4,7]=\text{query}(7)-\text{query}(3)$. Before the update $\text{query}(7)=16$; the $+4$ landed on $a_5$, which is inside prefix $7$, so new $\text{query}(7)=16+4=20$. $\text{query}(3)$: $3=0011_2\to 3\stackrel{-1}{\to }2\stackrel{-2}{\to }0$, cells $\text{tree}[3]+\text{tree}[2]$.

• $\text{tree}[3]=a_3=-1$, $\text{tree}[2]=a_1+a_2=5$. So $\text{query}(3)=4$. (Index $3<5$, unaffected by the update.) $[4,7]=20-4===16==.$ Direct check: $a_4+a_5+a_6+a_7=6+(5+4)+4-3=6+9+4-3=16$. ✓

Update path (moves up, $j+=\text{lowbit}(j)$): the worst case starts small and climbs. Starting at $j=1$: $1\to 2\to 4\to 8\to 16\to$ stop — that's $5$ cells touched. Every doubling adds one step, so the length is $\lfloor {\log }_{2}n\rfloor +1=5$ for $n=16$. Any odd index near $1$ (e.g. $1$) hits this bound. Query path (moves down, strips one $1$-bit each step): longest for the index with the most set bits $\le n$. For $n=16$ that's $15=1111_2$ (four $1$-bits) → path $15\to 14\to 12\to 8\to 0$, 4 cells. (Index $16=10000_2$ has only one bit → path length $1$.)

Each query step does $i\leftarrow i-\text{lowbit}(i)$. Subtracting the lowest set bit from $i$ clears exactly that one bit (it turns the rightmost $1$ into $0$ and touches nothing else, since $\text{lowbit}(i)$ is a pure power of two aligned to that bit). The loop stops when $i=0$, i.e. when all $1$-bits are gone. Therefore the number of iterations = number of $1$-bits initially present = $\text{popcount}(i)$. Since $\text{popcount}(i)\le \lceil {\log }_2(i+1)\rceil \le {\log }_{2}n+1$, the query is $O(\log n)$. $■$

$\text{lowbit}(0)=0\&(-0)=0\&0=0$. The update step $j\leftarrow j+\text{lowbit}(j)=0+0=0$ never changes $j$. So the loop condition j <= n stays true forever → infinite loop (or, if you guard it, the update silently does nothing). It's silent because no exception fires; the code just spins or no-ops. 1-indexing dodges it: real element indices become $1,2,\dots ,n$, never $0$. Every valid index has a lowest set bit, so both loops always progress. (See parent lowbit insight.)

Idea: scan left to right; before inserting $p_j$, ask "how many already-inserted values are greater than $p_j$?" Those form inversions with $j$. A Fenwick over value slots gives how many inserted are $\le v$ via a prefix query; greater-than count $=$ (inserted so far) $-$ prefix$(p_j)$.

Start with empty tree over slots $\mathrm{1..4}$. Let $c$ = number inserted so far.

(At step 4, values $\le 2$ inserted = just the $1$, so $\text{query}(2)=1$; the $3$ and $4$ are both greater → $2$ inversions.) $\text{total inversions}=0+1+0+2===3==.$ Check by hand: the pairs are $(3,1),(3,2),(4,2)$ — exactly $3$. ✓

Difference trick: keep a Fenwick over a difference array $d$ where the point read is a prefix sum of $d$. To add $\delta$ on $[l,r]$: do update(l, +δ) and update(r+1, -δ). Then read(k) = query(k) (prefix sum) gives the current value at $k$, because the $+\delta$ turns on at $l$ and the $-\delta$ turns it off after $r$.

Apply add(2,4,+5) on size-$5$ zero array: update(2,+5), update(5,-5) (since $r+1=5$).

• read(3) = query(3) = sum of $d[\mathrm{1..3}]$ = $+5$ (the $+5$ at slot $2$ is included, the $-5$ at slot $5$ is not). → $==5==$. Correct: index $3\in [2,4]$.
• read(5) = query(5) = $+5-5===0==$. Correct: index $5\notin [2,4]$.

Binary lifting walks the tree from the top power-of-two down, greedily jumping right while the accumulated count stays $<k$. We want the smallest index whose prefix count $\ge k=4$. Counts by slot: slot2=1, slot3=2, slot6=1, slot8=1 (others $0$). The Fenwick cells (block sums) are what we actually read, but conceptually we track a running total acc and current position pos=0. Highest power of two $\le n=8$ is $8$. Try jumps $8,4,2,1$:

• jump $+8$: cell $[1,8]$ sum $=5$. $acc+5=5\ge 4$? Yes → don't take it (we'd overshoot). Stay.
• jump $+4$: cell $[1,4]$ sum $=$ slot2+slot3 $=3$. $acc+3=3<4$ → take. pos=4, acc=3.
• jump $+2$: cell $[5,6]$ sum $=1$. $acc+1=4$. Is $4<4$? No → don't take.
• jump $+1$: cell $[7,7]$ sum $=0$. $acc+0=3<4$ → take. pos=5, acc=3. Answer index $=pos+1===6==$. Check: sorted present multiset is $[2,3,3,6,8]$; the $4$th smallest is $6$. ✓

Single element: $a_i=\text{query}(i)-\text{query}(i-1)$, but we can recover directly. For a cell whose block has length $>1$, subtract the sub-blocks it swallowed. The clean rule: $a_i=\text{tree}[i]-\sum \text{tree}[k]$ where $k$ ranges over the children $k=i-1,i-1-\text{lowbit}(i-1),\dots$ down to $i-\text{lowbit}(i)$. Easiest here is $a_i=\text{query}(i)-\text{query}(i-1)$. Let's just run queries:

• $\text{query}(1)=\text{tree}[1]=3$ → $a_1=3$.
• $\text{query}(2)=\text{tree}[2]=5$ → $a_2=5-3=2$.
• $\text{query}(3)=\text{tree}[3]+\text{tree}[2]=-1+5=4$ → $a_3=4-5=-1$.
• $\text{query}(4)=\text{tree}[4]=10$ → $a_4=10-4=6$.
• $\text{query}(5)=\text{tree}[5]+\text{tree}[4]=5+10=15$ → $a_5=15-10=5$.
• $\text{query}(6)=\text{tree}[6]+\text{tree}[4]=9+10=19$ → $a_6=19-15=4$.
• $\text{query}(7)=\text{tree}[7]+\text{tree}[6]+\text{tree}[4]=-3+9+10=16$ → $a_7=16-19=-3$.
• $\text{query}(8)=\text{tree}[8]=19$ → $a_8=19-16=3$. $a=[3,2,-1,6,5,4,-3,3].$ (Our original array — the tree was built from it.) ✓

Claim: when the loop reaches index $i$, tree[i] already equals its correct block sum ${\sum }_{k=i-\text{lowbit}(i)+1}^i{a}_k$. Why: cell $i$'s block is composed of $a_i$ (its own initial value) plus the blocks of all immediate children — cells $c$ with $c+\text{lowbit}(c)=i$ and $c<i$. Each such child $c$ satisfies $c<i$, so it was processed earlier in the increasing loop and, by induction, was already complete when it "donated" tree[c] into tree[c+lowbit(c)] = tree[i]. By the time we read $i$ to donate upward, every child has finished contributing, so tree[i] is complete. The base case (leaf cells, $\text{lowbit}=1$) hold $a_i$ immediately with no children. Hence one increasing pass completes all cells. $■$ (Cost: each $i$ does one add → $O(n)$.)

Method: $a_k=\text{query}(k)-\text{query}(k-1)$. Each query is $O(\log n)$, so the difference is $O(\log n)$. (A slicker $O(\log n)$ walk that subtracts overlapping cells exists, but two queries is simplest and same asymptotics.) For $k=6$: from L5.1, $\text{query}(6)=19$ and $\text{query}(5)=15$, so $a_6=19-15===4==.$ ✓

Query direction? ::: subtract lowbit, move toward $0$. Update direction? ::: add lowbit, move toward $n$. $a_i$ from a built tree? ::: $\text{query}(i)-\text{query}(i-1)$.