Let, $f$ be some *reversible* function and $A$ be an array of integers of length $N$.

Fenwick tree is a data structure which:

- calculates the value of function $f$ in the given range $[l; r]$ (i.e. $f(A_l, A_{l+1}, \dots, A_r)$) in $O(lg\ n)$ time;
- updates the value of an element of $A$ in $O(lg\ n)$ time;
- requires $O(N)$ memory, or in other words, exactly the same memory required for $A$;
- is easy to use and code, especially, in the case of multidimensional arrays.

Fenwick tree is also called Binary Indexed Tree.

The most common application of Fenwick tree is *calculating the sum of a range* (i.e. $f(A_1, A_2, \dots, A_k) = A_1 + A_2 + \dots + A_k$).

Fenwick tree was first described in a paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).

For the sake of simplicity, we will assume that function $f$ is just a *sum function*.

Given an array of integers $A[0 \dots N-1]$. Fenwick tree is an array $T[0 \dots N-1]$, where each of its elements is equal to the sum of elements of $A$ in some range $[g(i); i]$:

$$T_i = \sum_{j = g(i)}^{i}{A_j}$$

where $g$ is some function that satisfies $(g(i) \le i)$ and we will define it a bit later.

Note:Fenwick tree presented heredoes support0-based indexing (in case you were told that it does not support it).

Now we can write pseudo-code for the two operations mentioned above — get the sum of elements of $A$ in range $[0; r]$ and update some element $A_i$:

```
def sum (int r):
res = 0
while (r >= 0):
res += t[r]
r = g(r) - 1
return res
def inc (int i, int delta):
for all j, where g(j) <= i <= j
t[j] += delta
```

The function `sum`

works as follows:

- first, it adds the sum of the range $[g(r); r]$ (i.e. $T[r]$) to the
`result`

- then, it "jumps" to the range $[g(g(r)-1); g(r)-1]$, and adds this range's sum to the
`result`

- and so on, until it "jumps" from $[0; g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1); -1]$; that is where the
`sum`

function stops jumping.

The function `inc`

works with the same analogy, but "jumps" in the direction of increasing indices:

- sums of the ranges $[g(j); j]$ that satisfy the condition $g(j) \le i \le j$ are increased by
`delta`

, that is`t[j] += delta`

.

It is obvious that complexity of both `sum`

and `upd`

do depend on the function $g$. We will define the function $g$ in such a way that both of the operations have a logarithmic complexity $O(lg N)$.

**Definition of $g(i)$.** Let us consider the least significant digit of $i$ in binary. If this digit is $0$, then let $g(i) = i$. Otherwise, the binary representation of $i$ will end with at least one $1$ bit. We will flip all these tailing $1$'s (so they become $0$'s) and define the result as a value of $g(i)$.

There exists a trivial solution for the non-trivial operation described above:

```
g(i) = i & (i+1)
```

where `&`

is a logical AND operator. It is not hard to convince yourself that this solution does the same thing as the operation described above.

Now, we need to find a way to find all $j$'s, such that *g(j) <= i <= j*.

It is easy to see that we can find all such $j$'s by starting with $i$ and flipping the least significant zero bit. For example, for $i = 10$ we have:

```
j = 10, binary 0001010
j = 11, binary 0001011
j = 15, binary 0001111
j = 31, binary 0011111
j = 63, binary 0111111
...
```

Unsurprisingly, there also exists a simple way to do the above operation:

```
h(j) = j | (j+1)
```

where `|`

is a logical OR operator.

```
struct FenwickTree {
vector<int> bit; // binary indexed tree
int n;
void init(int n) {
this->n = n;
bit.assign(n, 0);
}
int sum(int r) {
int ret = 0;
for (; r >= 0; r = (r & (r+1)) - 1)
ret += bit[r];
return ret;
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx+1))
bit[idx] += delta;
}
int sum(int l, int r) {
return sum(r) - sum(l-1);
}
void init(vector<int> a) {
init(a.size());
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
};
```

It is obvious that there is no way of finding minimum of range $[l; r]$ using Fenwick tree, as Fenwick tree can only answer queries of type [0; r]. Additionally, each time a value is `update`

'd, new value should be smaller than the current value (because, the $min$ function is not reversible). These, of course, are significant limitations.

```
struct FenwickTreeMin {
vector<int> bit;
int n;
const int INF = (int)1e9;
void init (int n) {
this->n = n;
bit.assign (n, INF);
}
int getmin (int r) {
int ret = INF;
for (; r >= 0; r = (r & (r+1)) - 1)
ret = min(ret, bit[r]);
return ret;
}
void update (int idx, int val) {
for (; idx < n; idx = idx | (idx+1))
bit[idx] = min(bit[idx], val);
}
void init (vector<int> a) {
init (a.size());
for (size_t i = 0; i < a.size(); i++)
update(i, a[i]);
}
};
```

As claimed before, it is easy to implement Fenwick Tree for multidimensional array.

```
struct FenwickTree2D {
vector <vector <int> > bit;
int n, m;
// init(...) { ... }
int sum (int x, int y) {
int ret = 0;
for (int i = x; i >= 0; i = (i & (i+1)) - 1)
for (int j = y; j >= 0; j = (j & (j+1)) - 1)
ret += bit[i][j];
return ret;
}
void add(int x, int y, int delta) {
for (int i = x; i < n; i = i | (i+1))
for (int j = y; j < m; j = j | (j+1))
bit[i][j] += delta;
}
};
```

- UVA 12086 - Potentiometers
- LOJ 1112 - Curious Robin Hood
- LOJ 1266 - Points in Rectangle
- Codechef - SPREAD
- SPOJ - CTRICK
- SPOJ - MATSUM
- SPOJ - DQUERY
- SPOJ - NKTEAM
- SPOJ - YODANESS
- SRM 310 - FloatingMedian