Fenwick tree

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Fenwick tree
Binary indexed tree
BITDemo.gif
Creation of a binary indexed tree for the array [1, 2, 3, 4, 5] by elementwise insertion
Typetree
Invented1989
Invented byBoris Ryabko
Time complexity in big O notation
Algorithm Average Worst case
Space O(n) O(n)
Search O(logn) O(logn)
Insert O(logn) O(logn)
Delete O(logn) O(logn)

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 Boris Ryabko in 1989[1] with a further modification published in 1992.[2] It has subsequently become known under the name Fenwick tree after Peter Fenwick, who described this structure in his 1994 article.[3]

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. A flat array of numbers 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 is number of dimensions and is the number of elements along each dimension.[4]

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 that contain the modified value are in turn modified during a similar traversal of the tree. The range sums are defined such 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 corresponding 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 that 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 that may need to be updated is limited by the number of bits in the size of the array.

Implementation[edit]

Basic implementation in C[edit]

// SIZE should be 1 + a power of 2.
int A[SIZE];

// Least Significant Bit of i
#define LSB(i) ((i) & -(i))

// Returns the sum of the first i elements (indices 0 to i)
// Equivalent to range_sum(0, i)
int prefix_sum(int i) {
	int sum = A[0];
	for (; i != 0; i -= LSB(i))
		sum += A[i];
	return sum;
}

// Add delta to element with index i (zero-based)
void add(int i, int delta) {
	if (i == 0) {
		A[0] += delta;
		return;
	}
	for (; i < SIZE; i+= LSB(i))
		A[i] += delta;
}

Useful functions in C[edit]

// Returns the sum of elements from i + 1 to j
// Equivalent to prefix_sum(j) - prefix_sum(i), but slightly faster
int range_sum(int i, int j) {
	int sum = 0;
	for (; j > i; j -= LSB(j))
		sum += A[j];
	for (; i > j; i -= LSB(i))
		sum -= A[i];
	return sum;
}

// Convert A[] in place to Fenwick tree form
void init(void) {
	for (int i = 1; i < SIZE; ++i) {
		int j = i + LSB(i);
		if (j < SIZE)
			A[j] += A[i];
	}
}

// Convert back to array of per-element counts
void fini(void) {
	for (int i = SIZE - 1; i > 0; --i) {
		int j = i + LSB(i);
		if (j < SIZE)
			A[j] -= A[i];
	}
}

// Return a single element's value
int get(int i) {
	return range_sum(i, i + 1);
}

// Set (as opposed to adjust) a single element's value
void set(int i, int value) {
	add(i, value - get(i));
}

// Find the largest i with prefix_sum(i) <= value.
// NOTE: Requires that all values are non-negative!
unsigned int rank_query(int value) {
	int i = 0, j = SIZE - 1;
	// j is a power of 2.

    value -= A[0];
	for (; j > 0;  j >>= 1) {
		if (i + j < SIZE && A[i + j] <= value) {
			value -= A[i + j];
			i += j;
		}
	}
	return i;
}

Implementation in C++[edit]

class FenwickTree {
private:
    vector<int> data;

    int getParent(int i) const {
        return i - (i & (-i));
    }

    int getNext(int i) const {
        return i + (i & (-i));
    }

public:
    FenwickTree(int n) : data(n+1, 0) {
    }

    int getSum(int i) const {
        int sum = 0;
        ++i;
        while (i > 0) {
            sum += data[i];
            i = getParent(i);
        }
        return sum;
    }

    void update(int i, int v) {
        ++i;
        while (i < data.size()) {
            data[i] += v;
            i = getNext(i);
        }
    }
};

Updating and querying the tree[edit]

The following table describes various ways in which Fenwick tree can be used. More importantly, it states the right API to be called or used in order to achieve the desired result along with an example explaining the use case.

Binary indexed tree operation combination and corresponding algorithm
Test type code Update operation Query operation Algorithm Corresponding APIs to execute
1 Point update Point query (frequency) Update and query on single BIT array
Update(BIT1,  index, value)
Query(BIT1, index) - Query(BIT1, index - 1)}}
Comment
Alternative 1: Query(index) using common ancestor technique.
Alternative 2: This query can be answered in O(1) time by trading off for O(n) space.
Example
A := [1 2 3 4 5]
Update(2, 3) = [1 5 3 4 5]
Query(2) = 5, Query(3) = 3}}
2 Point update Point query (cumulative frequency) Update and query on single BIT array
Update(BIT1,  index, value)
Query(BIT1, index)}}
Example
A := [1 2 3 4 5]
Update(2, 3) = [1 5 3 4 5]
Query(2) = 6, Query(3) = 9}}
3 Point update Range query (frequency) Update and query on single BIT array Perform operation 1 on each index in the range
Range := [L, R]
Update(BIT1, index, value)
for(index from L to R) {
  Query(BIT1, index) - Query(BIT1, index - 1)
}
Comment

This condition is ideally not interesting, but has to be covered in order to cover all scenarios and to also give one concrete meaning to this scenario. Others can have their own definition. This query can be answered in O(k) time by trading off for O(n) space.

Example
A := [1 2 3 4 5]
Update(2, 3) = [1 5 3 4 5]
Query(2, 4) = [5 3 4]
4 Point update Range query (cumulative frequency) Update and query on single BIT array
Range := [L, R]
Update(BIT1, index, value)
Query(BIT1, R) - Query(BIT1, L - 1)
Example
A := [1 2 3 4 5]
Update(2, 3) = [1 5 3 4 5]
Query(2, 4) = Query(4) - Query(1) = 12
5 Range update Point query (frequency) Update and query on two BIT arrays
Range := [L, R]
Update(BIT1, L, value)
Update(BIT1, R + 1, -value)
Update(BIT2, L, (L - 1) * value)
Update(BIT2, R + 1, -value * R)
Query(BIT1, BIT2, index) - Query(BIT1, BIT2, index - 1)}}
Comment

Operation 1 techniques does not apply here.

Query(BIT1, BIT2, index) = index * sum(BIT1, index) - sum(BIT2, index)
Example
A := [1 2 3 4 5]
Update(2, 4, 3) = [1 5 6 7 5]
Query(2) = 5, Query(3) = 6
6 Range update Point query (cumulative frequency) Update and query on two BIT arrays
Range := [L, R]
Update(BIT1, L, value)
Update(BIT1, R + 1, -value)
Update(BIT2, L, (L - 1) * value)
Update(BIT2, R + 1, -value * R)
Query(BIT1, BIT2, index)}}
Comment
Query(BIT1,  BIT2, index) = index * sum(BIT1, index) - sum(BIT2, index)
Example
A := [1 2 3 4 5]
Update(2, 4, 3) = [1 5 6 7 5]
Query(2) = 6, Query(3) = 12
7 Range update Range query (frequency) Update and query on two BIT arrays

Perform operation 1 on each index in the range

Range := [L, R]
Update(BIT1, L, value)
Update(BIT1, R + 1, -value)
Update(BIT2, L, (L - 1) * value)
Update(BIT2, R + 1, -value * R)
for(index from L to R) {
  Query(BIT1, BIT2, index) -  Query(BIT1, BIT2, index - 1)
}
Comment
Query(BIT1,  BIT2, index) = index * sum(BIT1, index) - sum(BIT2, index)
Example
A := [1 2 3 4 5];
Update(2, 4, 3) = [1 5 6 7 5]
Query(2, 4) = [5 6 7]}}
8 Range update Range query (cumulative frequency) Update and query on two BIT arrays
Range := [L, R]
Update(BIT1, L, value)
Update(BIT1, R + 1, -value)
Update(BIT2, L, (L - 1) * value)
Update(BIT2, R + 1, -value * R)
Query(BIT1, BIT2, R) - Query(BIT1, BIT2, L - 1)}}
Comment
Query(BIT1,  BIT2, index) = index * sum(BIT1, index) - sum(BIT2, index)
Example
A := [1 2 3 4 5]
Update(2, 4, 3) = [1 5 6 7 5]
Query(2, 4) = Query(4) - Query(1) = 18}}

See also[edit]

References[edit]

  1. ^ Boris Ryabko (1989). "A fast on-line code" (PDF). Soviet Math. Dokl. 39 (3): 533–537.
  2. ^ Boris Ryabko (1992). "A fast on-line adaptive code" (PDF). IEEE Transactions on Information Theory. 28 (1): 1400–1404.
  3. ^ Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables". Software: Practice and Experience. 24 (3): 327–336. CiteSeerX 10.1.1.14.8917. doi:10.1002/spe.4380240306.
  4. ^ Pushkar Mishra (2013). "A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays". arXiv:1311.6093. doi:10.13140/RG.2.1.2394.2485. Cite journal requires |journal= (help)

External links[edit]