# Fenwick Tree

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

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$.

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

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

- Update $tree[i]$
- Increment $i$ by $p(i)$
- Repeat until $i$ is out of bounds, i.e. while $i≤n$

### Implementation (1-indexed)

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

#### Variants (to master)

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

- Point Update and Range Query (Default)
- Range Update and Point Query
- 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]=sum_{q}(k−p(k)+1,k)$