# Fenwick Tree

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

### Description

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 here does support 0-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:

1. first, it adds the sum of the range $[g(r); r]$ (i.e. $T[r]$) to the result
2. then, it "jumps" to the range $[g(g(r)-1); g(r)-1]$, and adds this range's sum to the result
3. 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:

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

### Implementation: finding sum in one-dimensional array

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++)
}
};


### Implementation: finding minimum of $[0; r]$ in one-dimensional array

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]);
}
};


### Implementation: finding sum in two-dimensional array

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;
}
};