Fenwick Tree

The Fenwick Tree is a data structure that maintains a sequence of $n$ numbers $a_0,a_1,\dots ,a_{n-1}$ by maintaining

$$s(i)=\sum _{j=i-\mathrm{lsb}i}^{i-1}{a}_i$$

This requires $\mathcal{O}(n)$ space.

Add

Add updates $a_i$ to $a_i+x$ in $\mathcal{O}(\log n)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

Let $S_i=\{i-\mathrm{lsb}i,i-\mathrm{lsb}i+1,\dots ,i-1\}$, then

$$\forall i\in \mathbb{N},S_i\subseteq S_{i+\mathrm{lsb}i}$$

Proof

Let $i=2^{k+1}s+2^k$, then $\mathrm{lsb}i=2^k,i+\mathrm{lsb}i=2^{k+1}(s+1)$.

$$\begin{array}{rl}i+\mathrm{lsb}i=2^{k+1}(s+1)& ⟹\mathrm{lsb}(i+\mathrm{lsb}i)\ge 2^{k+1}\\ & ⟺i+\mathrm{lsb}i-\mathrm{lsb}(i+\mathrm{lsb}i)\le 2^{k+1}s\\ & ⟺i+\mathrm{lsb}i-\mathrm{lsb}(i+\mathrm{lsb}i)\le i-\mathrm{lsb}i\end{array}$$

Lemma

$$\forall i\in \mathbb{N},\forall j\in \{i+1,i+2,\dots ,i+\mathrm{lsb}i-1\},S_i\cap S_j=\varnothing$$

Proof

Let $i=2^{k+1}s+2^k,j=2^{k+1}s+2^k+t$, then $\mathrm{lsb}j=\mathrm{lsb}t$.

$$\begin{array}{rl}j-\mathrm{lsb}j& =2^{k+1}s+2^k+t-\mathrm{lsb}t\\ & \ge 2^{k+1}s+2^k\\ & =i\end{array}$$

Applying the lemmas to update $s$ yields an algorithm that solves the problem in $\mathcal{O}(\log n)$ time and $\mathcal{O}(1)$ space.

void add(int i, int x) {
	for (int j = i + 1; j <= n; j += j & -j) {
		s[j] += x;
	}
}

Sum

Sum computes ${\sum }_{j=0}^{i-1}{a}_j$ in $\mathcal{O}(\log n)$ time and $\mathcal{O}(1)$ space.

Algorithm

0. Find ${\sum }_{j=0}^{i-\mathrm{lsb}i-1}{a}_j$ recursively.
1. ${\sum }_{j=0}^{i-1}{a}_j={\sum }_{j=0}^{i-\mathrm{lsb}i-1}{a}_j+s(i)$.

This algorithm solves the problem in $\mathcal{O}(\log n)$ time and $\mathcal{O}(1)$ space.

int sum(int i) {
	int res = 0;
	for (int j = i; j > 0; j -= j & -j) {
		res += s[j];
	}
	return res;
}