Tree Data Structure

Fenwick Tree

A Fenwick/Binary-Indexed tree can both process range sum queries and update values real-time in $O(\log n)$.

I still don’t fully grasp why it works, but I grasp the algorithm.

To process a query, we use this formula: $p(k)=k\&-k$ which gets the rightmost set bit of $k$.

1. Add $tree[k]$ to a running sum
2. Decrement $k$ by $p(k)$, which subtracts its rightmost set bit
3. Repeat until $k$ reaches 0
4. Return the running sum

To update a value at index i, we only update certain indices of the tree:

1. Update $tree[i]$
2. Increment $i$ by $p(i)$
3. Repeat until $i$ is out of bounds, i.e. while $i\le n$

Implementation (1-indexed)

This is the default implementation that supports range queries and point updates.

int sum(int k) { 
	int s = 0; 
	while (k > 0) { 
		s += tree[k]; 
		k -= k&-k; 
	} 
	return s;
}
 
int range_sum(int l, int r) {
	return sum(r) - sum(l-1);
}
 
void update(int i, int x) { 
	while (i <= n) { 
		tree[i] += x; 
		i += i&-i; 
	} 
}

Variants (to master)

The following are variants of Fenwick trees that need extra work.

1. Point Update and Range Query (Default)
2. Range Update and Point Query
3. Range Update and Range Query

Extra

This below is confusing to me, but I think it’s still good information. Each value of $tree[k]$ corresponds to $tree[k]=su{m}_q(k-p(k)+1,k)$

Related

• Segment Tree