Wood Fenwick

Fenwick tree - a data structure, a tree on the array with the following properties:

1) allows to calculate the value of a reversible operation of G on any interval [L; R] in time O (log N);

2) lets you change the value of any element in O (log N);

3) requires O (N) memory, or more precisely, exactly the same as, and an array of N elements;

4) is easily generalized to the case of multidimensional arrays.

The most common use of wood Fenwick - to calculate the sum of the segment, ie function G (X1, ..., Xk) = X1 + ... + Xk.

Wood Fenwick was first described in the article "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
Description

For ease of description, we assume that the operation of G, on which we build a tree - a sum.

Suppose we are given an array A [0 .. N-1]. Fenwick tree - an array T [0 .. N-1], each element of which is stored the sum of some elements of the array A:

Ti = the sum of Aj for all F (i) <= j <= i,

where F (i) - a function which we define later.

Now we can write the pseudocode for the function computing the sum on the interval [0; R], and changes in cell function:

int sum (int r)
{
int result = 0;
while (r> = 0) {
result + = t [r];
r = f (r) - 1;
}
return result;
}

void inc (int i, int delta)
{
for all j, for which F (j) <= i <= j
{
t [j] + = delta;
}
}

The sum function works as follows. Instead of going through all elements of the array A, it moves over the array of T, making the "jump" across the segments where possible. First, it adds to the response value of the sum on the interval [F (R); R], then takes the sum of the interval [F (F (R) -1); F (R) -1], and so on, until it reaches zero.

The function inc is moving in the opposite direction - toward increasing index, updating the value of the sum Tj only for those positions for which this is necessary, ie for all j, for which F (j) <= i <= j.

Obviously, the choice of F will depend on the speed of both operations. Now we consider a function that would achieve logarithmic performance in both cases.

We define the value of F (X) as follows. Consider the binary representation of numbers and look at its lowest bit. If it is zero, then F (X) = X. Otherwise, the binary representation of X ends in a group of one or more units. We replace all the units from this group on the zeros, and assign that number to the value of the function F (X).

This is a rather complicated description corresponds to a very simple formula:

F (X) = X & (X +1),

where k - is the bitwise logical "AND".

It is easy to see that this formula corresponds to the verbal description of the function given above.



We just have to learn how to quickly find the number of such j, for which F (j) <= i <= j.

However, it is easy to verify that all such numbers j are obtained from i by successive replacements of the rightmost (least significant) zero in the binary representation. For example, for i = 10, we find that j = 11, 15, 31, 63, etc.

Ironically, such an operation (replacement of the youngest unit of zero) and corresponds to a very simple formula:

H (X) = X | (X +1),

where | - is a bitwise logical "OR".
The implementation of the tree Fenwick for the sum of one-dimensional case

vector <int> t;
int n;

void init (int nn)
{
n = nn;
t.assign (n, 0);
}

int sum (int r)
{
int result = 0;
for (; r> = 0; r = (r & (r +1)) - 1)
result + = t [r];
return result;
}

void inc (int i, int delta)
{
for (; i <n; i = (i | (i +1)))
t [i] + = delta;
}

int sum (int l, int r)
{
return sum (r) - sum (l-1);
}

void init (vector <int> a)
{
init ((int) a.size ());
for (unsigned i = 0; i <a.size (); i + +)
inc (i, a [i]);
}

The implementation of the tree Fenwick for a minimum of one-dimensional case

It should be noted immediately that, since the Fenwick tree allows you to find the value of the function in an arbitrary interval [0; R], then we will not be able to find the minimum on the interval [L; R], where L> 0. Further, the values ​​of all the changes should take place only in the direction of decreasing (again, because it does not get to draw the function min). This is a significant limitation.

vector <int> t;
int n;

const int INF = 1000 * 1000 * 1000;

void init (int nn)
{
n = nn;
t.assign (n, INF);
}

int getmin (int r)
{
int result = INF;
for (; r> = 0; r = (r & (r +1)) - 1)
result = min (result, t [r]);
return result;
}

void update (int i, int new_val)
{
for (; i <n; i = (i | (i +1)))
t [i] = min (t [i], new_val);
}

void init (vector <int> a)
{
init ((int) a.size ());
for (unsigned i = 0; i <a.size (); i + +)
update (i, a [i]);
}

The implementation of the tree Fenwick for the sum of two-dimensional case

As already noted, the Fenwick tree can easily be generalized to the multidimensional case.

vector <vector <int>> t;
int n, m;

int sum (int x, int y)
{
int result = 0;
for (int i = x; i> = 0; i = (i & (i +1)) - 1)
for (int j = y; j> = 0; j = (j & (j +1)) - 1)
result + = t [i] [j];
return result;
}

void inc (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)))
t [i] [j] + = delta;
}