Fenwick Tree

• https://en.wikipedia.org/wiki/Fenwick_tree

Intro

• Fenwick tree or binary indexed tree (BIT) is a data structure that stores an array of values and can efficiently compute prefix sums of the values and update the values

• Its primary use is operating on the cumulative distribution function of a statistical frequency table which is updated often.

• But it can be used to write Log-Linear Attention efficiently in connection with structured matrices!

Problem it solves.

• Problem : maintain an array that must answer many prefix‑sum queries (sum[1..i]) while also supporting single‑element updates (a[k] += Δ).
• Naïve solutions :

Approach	Query	Update	Space
Re‑scan whole range	O(i)	O(1)	O(n)
Maintain full prefix array	O(1)	O(n)	O(n)

Fenwick Tree : stores cleverly chosen partial sums so that both operations run in O(log n) time and only O(n) space.

Intuition and implementation

• We will assume that the array is 1-indexed i.e. the first index is equal to 1

• An important definition is the least-significant bit of an integer $i$.

  • It is the largest power of two that divides $i$. It’s the right-most bit in the binary representation
  • i=6 , i_b=110 ⇒ `lowbit(6)= 2
  • It can be defined as lowbit(i) = i & (-i) (assuming two’s complement)

• Given an input array $a$ of length $N$, our Fenwick “Tree” (which internally can be represented by an array) will store an array $t$ of length $N$ such that $T[i]=sum(a[i-lowbit(i)-1,\dots ,i])$ stores a partial sum of block size equal to lowbit(i).

• As long as this invariant holds, then we can have:

lowbit(i)        = i & -i
update(k,Δ):     for(i=k; i<=n; i+=lowbit(i))  T[i]+=Δ
query(i):        for(i; i>0; i-=lowbit(i))     s+=T[i]
range(l,r):      query(r) - query(l-1)

• Point update / prefix query = O(log n) because each hop clears one binary digit.

Example

Zoom-in on the “blocks” idea — step by step

We’ll use an 8-element array so every block-size shows up at least once.

Position i	Binary of i	lowbit(i)	Block size	Block covers
1	001	1	1	[1]
2	010	2	2	[1‥2] ending at 2
3	011	1	1	[3]
4	100	4	4	[1‥4] ending at 4
5	101	1	1	[5]
6	110	2	2	[5‥6]
7	111	1	1	[7]
8	1000	8	8	[1‥8]

Walkthrough with concrete numbers

Suppose the array a is

i : 1  2 3 4 5 6 7 8
a : 2  1 3 7 9 4 5 2

1. Build the internal tree array T[1..8]

We’ll insert each element with add(i, a[i]).

Operation	i path (+= lowbit)	Tree cells touched	After update (T)
add(1,2)	1 → 2 → 4 → 8	1, 2, 4, 8	T₁ = 2, T₂ = 2, T₄ = 2, T₈ = 2
add(2,1)	2 → 4 → 8	2, 4, 8	T₂ = 3, T₄ = 3, T₈ = 3
add(3,3)	3 → 4 → 8	3, 4, 8	T₃ = 3, T₄ = 6, T₈ = 6
add(4,7)	4 → 8	4, 8	T₄ = 13, T₈ = 13
add(5,9)	5 → 6 → 8	5, 6, 8	T₅ = 9, T₆ = 9, T₈ = 22
add(6,4)	6 → 8	6, 8	T₆ = 13, T₈ = 26
add(7,5)	7 → 8	7, 8	T₇ = 5, T₈ = 31
add(8,2)	8	8	T₈ = 33

Final tree (index : value):

1:2  2:3  3:3  4:13  5:9  6:13  7:5  8:33

Interpreting a couple of cells:

• T₆ = 13 stores a[5]+a[6] (block [5,6], size 2).

• T₄ = 13 stores a[1]+a[2]+a[3]+a[4] (block [1‥4], size 4).

2. Query example: prefix sum up to position 6

Goal: S = a₁+⋯+a₆ (should be 2+1+3+7+9+4 = 26).

i = 6:  S += T6 (13)   → S = 13;   i -= lowbit(6)=2 → i=4
i = 4:  S += T4 (13)   → S = 26;   i -= lowbit(4)=4 → i=0
stop

Two steps, two block adds → O(log n).

3. Point update: add +6 to a[5] (so a[5] becomes 15)

add(5, +6):
   i=5 → T5 +=6  (9→15); i=6
   i=6 → T6 +=6  (13→19); i=8
   i=8 → T8 +=6  (33→39); i=16>n stop

Only three cells changed; complexity again log n.

Why this invariant works

• The indices you visit while climbing upward (i += lowbit(i)) are exactly those whose blocks contain the point being updated.

• The indices you visit while peeling down (i -= lowbit(i)) partition the prefix [1..q] into disjoint blocks.

Both traversals change or use ≤ ⌈log₂ n⌉ blocks because each step removes the least-significant 1, effectively jumping to the parent in a binary-tree view of the index.

Visualising with binary

   1000 (8) ┐
      │     ├── covers 1..8
   0100 (4) ┘
      │     ├── covers 1..4
   0010 (2) ┘
      │     ├── covers 5..6
   0001 (1) ┘

Every i is the root of a subtree whose size is lowbit(i); updates walk upwards, queries walk leftwards toward 0.

Key take-aways

• lowbit is both block size and stride.

• The tree stores partial sums of power-of-two blocks ending at each index.

• Point update / prefix query = logarithmic because each hop clears one binary digit.