Fenwick Tree

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

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

which costs a space of $\mathcal{O}(n)$.

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

Lemma

$$\forall i\in \{1,2,\dots ,n\},\sum _{j=0}^{i-1}{a}_j=s(i)+\sum _{j=0}^{i-\mathrm{lsb}(i)-1}{a}_j$$

Applying the lemma to find ${\sum }_{j=0}^{i-1}{a}_j$ yields an algorithm that 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;
}