Fenwick Tree / Binary Indexed Tree
Data Structure · Stretch
Step through it: Prefix Sum pattern
Now tap the end number.
Step 1 of 5
Question: what is 1 + 4 + 2? Adding three numbers is easy. But if someone asks 1,000 range questions, you re-add the same numbers again and again.
Step 2 of 5
The fix: walk left to right once and write a running total under each number. Each bottom box means everything from the start up to here. The small sum under it shows how it was built.
Step 3 of 5
Want 1 + 4 + 2? Look at the running total under the 2: it is 10. That is too much, because it counts 3 + 1 + 4 + 2 and includes an extra 3 at the front.
Step 4 of 5
Remove the extra part. The running total just before your range is 3, so 10 − 3 = 7. That is two lookups and one subtraction, however long the range is. This list of running totals is called a prefix sum.
Step 5 of 5
Your turn. Tap a start number, then an end number. Try starting at the first number to see the "nothing before" case.
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.
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 n 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 O(log n) 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 O(log n) node accesses.
Implementation Notes
Binary Indexed Tree is represented as an array. Each node of Binary Indexed Tree
stores sum of some elements of given array. Size of Binary Indexed Tree is equal
to n where n is size of input array. In current implementation we have used
size as n+1 for ease of implementation. All the indexes are 1-based.
On the picture below you may see animated example of
creation of binary indexed tree for the
array [1, 2, 3, 4, 5] by inserting one by one.
Code
export default class FenwickTree {
/**
* Constructor creates empty fenwick tree of size 'arraySize',
* however, array size is size+1, because index is 1-based.
*
* @param {number} arraySize
*/
constructor(arraySize) {
this.arraySize = arraySize;
// Fill tree array with zeros.
this.treeArray = Array(this.arraySize + 1).fill(0);
}
/**
* Adds value to existing value at position.
*
* @param {number} position
* @param {number} value
* @return {FenwickTree}
*/
increase(position, value) {
if (position < 1 || position > this.arraySize) {
throw new Error('Position is out of allowed range');
}
for (let i = position; i <= this.arraySize; i += (i & -i)) {
this.treeArray[i] += value;
}
return this;
}
/**
* Query sum from index 1 to position.
*
* @param {number} position
* @return {number}
*/
query(position) {
if (position < 1 || position > this.arraySize) {
throw new Error('Position is out of allowed range');
}
let sum = 0;
for (let i = position; i > 0; i -= (i & -i)) {
sum += this.treeArray[i];
}
return sum;
}
/**
* Query sum from index leftIndex to rightIndex.
*
* @param {number} leftIndex
* @param {number} rightIndex
* @return {number}
*/
queryRange(leftIndex, rightIndex) {
if (leftIndex > rightIndex) {
throw new Error('Left index can not be greater than right one');
}
if (leftIndex === 1) {
return this.query(rightIndex);
}
return this.query(rightIndex) - this.query(leftIndex - 1);
}
}References
Practice
Prefix Sum
- Running Sum of 1d ArrayEasy
- Range Sum Query - ImmutableEasy
- Find Pivot IndexEasy
- Find the Highest AltitudeEasy
- Subarray Sum Equals KMedium
- Product of Array Except SelfMedium
- Continuous Subarray SumMedium
- Contiguous ArrayMedium
- Range Sum Query 2D - ImmutableMedium
- Subarray Sums Divisible by KMedium
- Maximum Size Subarray Sum Equals kMedium
- Corporate Flight BookingsMedium
- Car PoolingMedium
- Maximum SubarrayMedium
- Count of Range SumHard
Spotted a mistake or something unclear? Report it on GitHub.