Fenwick tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Create a binary indexed tree for the array [1, 2, 3, 4, 5] by inserting one by one.

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Peter Fenwick in 1994 to improve the efficiency of arithmetic coding compression algorithms.[1]

When compared with a flat array of numbers, the Fenwick tree achieves a much better balance between two operations: element update and prefix sum calculation. In a flat array of numbers, you can either store the elements, or the prefix sums. In the first case, computing prefix sums requires linear time; in the second case, updating the array elements requires linear time (in both cases, the other operation can be performed in constant time). Fenwick trees allow both operations to be performed in time. This is achieved by representing the numbers as a tree, where the value of each node is the sum of the numbers in that subtree. The tree structure allows operations to be performed using only node accesses.

Motivation[edit]

Given a table of elements, it is sometimes desirable to calculate the running total of values up to each index according to some associative binary operation (addition on integers being by far the most common). Fenwick trees provide a method to query the running total at any index, in addition to allowing changes to the underlying value table and having all further queries reflect those changes.

Fenwick trees are particularly designed to implement the arithmetic coding algorithm, which maintains counts of each symbol produced and needs to convert those to the cumulative probability of a symbol less than a given symbol. Development of operations it supports were primarily motivated by use in that case.

Using a Fenwick tree it requires only operations to compute any desired cumulative sum, or more generally the sum of any range of values (not necessarily starting at zero).

Fenwick trees can be extended to update and query subarrays of multidimensional arrays. These operations can be performed with complexity , where d is number of dimensions and n is the number of elements along each dimension.[2]

Description[edit]

Although Fenwick trees are trees in concept, in practice they are implemented as an implicit data structure using a flat array analogous to implementations of a binary heap. Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through bitwise operations on the binary representation of its index. Each element of the array contains the pre-calculated sum of a range of values, and by combining that sum with additional ranges encountered during an upward traversal to the root, the prefix sum is calculated. When a table value is modified, all range sums which contain the modified value are in turn modified during a similar traversal of the tree. The range sums are defined in such a way that both queries and modifications to the table are executed in asymptotically equivalent time ( in the worst case).

The initial process of building the Fenwick tree over a table of values runs in time. Other efficient operations include locating the index of a value if all values are positive, or all indices with a given value if all values are non-negative. Also supported is the scaling of all values by a constant factor in time.

A Fenwick tree is most easily understood by considering a one-based array. Each element whose index i is a power of 2 contains the sum of the first i elements. Elements whose indices are the sum of two (distinct) powers of 2 contain the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, and that parent is found by clearing the least-significant bit in the index.

To find the sum up to any given index, consider the binary expansion of the index, and add elements which correspond to each 1 bit in the binary form.

For example, say one wishes to find the sum of the first eleven values. Eleven is 10112 in binary. This contains three 1 bits, so three elements must be added: 10002, 10102, and 10112. These contain the sums of values 1–8, 9–10, and 11, respectively.

To modify the eleventh value, the elements which must be modified are 10112, 11002, 100002, and all higher powers of 2 up to the size of the array. These contain the sums of values 11, 9–12, and 1–16, respectively. The maximum number of elements which may need to be updated is limited by the number of bits in the size of the array.

Implementation[edit]

A simple C implementation follows. The setup phase takes about 20% times longer than for a simple flat array, but the subsequent queries are (because of the large array used) about 1600 times faster.

/*******************************************************************/
/* This program demonstrates the speedup for a Fenwick tree vs a   */
/* flat array for performing multiple prefix sums.  It generates a */
/* sequence of random numbers, then performs 1000 summations,      */
/* each of which starts and ends at random indices.                */
/*******************************************************************/
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

// Number of elements in the array
#define N (4*1024*1024)		// Elements in the array
#define COUNTS 1024		// Size of values stored
typedef unsigned long sum_t;	// Should be able to hold N * (COUNTS - 1)

// Number of queries to perform
#define NQUERIES 1000

// Isolate the least significant 1 bit.  E.g. LEB(0x1234) == 4.
#define LSB(i) ((i) & -(i))

// Fen_sum: return the sum of the first i elements, 0 through i-1.
sum_t Fen_sum(sum_t const *a, unsigned int i) 
{
	sum_t sum = 0;
	while (i) {
		sum += a[i-1];
		i -= LSB(i);
	}
	return sum;
}

// Fen_add: add k to element i (and thus Fen_sum(a, j) for all j > i)
void Fen_add(sum_t *a, unsigned int size, sum_t delta, unsigned int i) 
{
	while (i < size) {
		a[i] += delta;
		i += LSB(i+1);
	}
}

// Fen_range: Returns the sum of the elements [i..j-1]
// This could be written as "Fen_sum(a, j) - Fen_sum(a, i)",
// but it is possible to do it in less time (particularly for
// small ranges) by avoiding the terms that the two sums have
// in common.
sum_t Fen_range(sum_t const *a, unsigned int i, unsigned int j)
{
	sum_t sum = 0;

	while (j > i) {
		sum += a[j-1];
		j -= LSB(j);
	}

	while (i > j) {
		sum -= a[i-1];
		i -= LSB(i);
	}
	return sum;
}

// Fen_get: Returns the value of the element at index i
// (The time is proportional to the number of trailing 1 bits
// in i.  So even numbers are fast, and i = 0xffff takes 16 steps.)
sum_t Fen_get(sum_t const *a, unsigned int i)
{
	return Fen_range(a, i, i+1);
}

// Fen_set: sets the value of the element at index i
void Fen_set(sum_t *a, unsigned int size, sum_t value, unsigned int i)
{
	Fen_add(a, size, value - Fen_get(a, i), i);
}

// It's possible to initialize a Fenwick tree using Fen_add or
// Fen_set (you can even do the latter in-place if you go backward
// through the array), but for bulk initialization, this is faster.
void Fen_init(sum_t *a, unsigned int size)
{
	for (unsigned int i = 0; i < size; i++) {
		unsigned int j = i + LSB(i+1);
		if (j < size)
			a[j] += a[i];
	}
}

// main: allocates an array of numbers and fills it with a sequence of
// random numbers, then performs a series of summations (queries).  It
// then repeats the process using a Fenwick tree rather than a flat
// array.  The sequence of random numbers and the bounds of each query
// are identical for the flat array and the Fenwick tree.  The time
// required to populate the data structure and the total time required
// for all queries is calculated and reported for the flat array and
// for the Fenwick tree.

int main(void)
{
	sum_t *a;
	unsigned int queries[NQUERIES*2];
	clock_t time1, time2, time3;
	time_t seed = time(NULL);

	// generate the bounds for all of the queries
	srandom(seed + 1);
	for (unsigned int i = 0; i < NQUERIES * 2; i += 2) {
		unsigned int q = random() % N, r = random() % N;
		bool reverse = q > r;

		queries[i +  reverse] = q;
		queries[i + !reverse] = r;
	}

	// allocate the array of sums
	a = malloc(N * sizeof *a);

	// The following loop forces all pages into memory (otherwise the
	// timing of the algorithm could include a lot of page faults)
	for (unsigned int i = 0; i < N; i++)
		a[i] = 0;

	/*****************************************************************/
	/*   FLAT ARRAY METHOD                                           */
	/*****************************************************************/

	time1 = clock();
	// Store random numbers in a flat array
	srandom(seed);
	for (unsigned int i = 0; i < N; i++)
		a[i] = random() % COUNTS;
	time2 = clock();	// time2 - time1 = time for setup
	// perform the queries
	for (unsigned int j = 0; j < NQUERIES * 2; j += 2) {
		sum_t asum = 0;
		for (unsigned int i = queries[j]; i < queries[j+1]; i++)
			asum += a[i];
		printf(" %lu", asum);
	}
	time3 = clock();	// time3 - time2 = time for queries

	printf("\nFlat Array:\n Build: %f\n Query: %f\n",
		(time2-time1)*(1.0/CLOCKS_PER_SEC),
		(time3-time2)*(1.0/CLOCKS_PER_SEC));

	/*****************************************************************/
	/*   FENWICK TREE METHOD                                         */
	/*****************************************************************/

	time1 = clock();
	// Store the same random numbers in a Fenwick tree
	srandom(seed);
	for (unsigned int i = 0; i < N; i++)
		a[i] = random() % COUNTS;
	Fen_init(a, N);
	time2 = clock();	// time2 - time1 = time for setup
	// perform the queries
	for (unsigned int j = 0; j < NQUERIES * 2; j += 2)
		printf(" %lu", Fen_range(a, queries[j], queries[j+1]));
	time3 = clock();	// time3 - time2 = time for queries

	printf("\nFenwick:\n Build: %f\n Query: %f\n",
		(time2-time1)*(1.0/CLOCKS_PER_SEC),
		(time3-time2)*(1.0/CLOCKS_PER_SEC));

	free(a);
	return 0;
}

See also[edit]

References[edit]

  1. ^ Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables" (PDF). Software: Practice and Experience. 24 (3): 327–336. CiteSeerX 10.1.1.14.8917Freely accessible. doi:10.1002/spe.4380240306. 
  2. ^ Pushkar Mishra (2013). "A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays". arXiv:1311.6093Freely accessible [cs.DS]. 

External links[edit]