Background Information: What is a Fenwick Tree?
A Fenwick tree is a way of representing the prefix sums of an array of numbers (basically, it makes it easy to get the sum of a contiguous run of numbers). A normal array has \$O(1)\$ access time, \$O(1)\$ modification time, and \$O(n)\$ summation time, and a prefix sum array has \$O(1)\$ access time, \$O(n)\$ modification time, and \$O(1)\$ summation time. This means that neither is fast enough if you are doing a lot of modifications and summations. Therefore, a data structure known as the Fenwick Tree or the Binary Indexed Tree serves as a comprimise, with \$O(\log n)\$ access, modification, and summation time.
The best way to understand a Fenwick Tree is 1-indexed. They are usually represented as arrays, but I will present them as trees for this example.
Let's say we have an array
[1, 5, 3, 7, 6, 2, 8, 5, 3]. A Fenwick Tree for 9 elements would look like this:
If we look at the labels in binary, B is a child of A if all digits to the left of and including A's least significant bit are the same in B. For example, 7 is 111, so it is in the subtree of 110, because 110's LSB is the second digit, and all digits up to the second digit are the same in 110 and 111. 111 is also in the subtree of 100, and 110 is in the subtree of 100. However, 111 is not in the subtree of 010 or 1000. Finally, elements with only one 1-bit are in the subtree of 0, which is a dummy value pretty much.
The value in each node is the sum of all elements between its index in the base array and the index in its parent (exclusive). For example, node 6 will contain the sum of elements 5 and 6. Node 4 will contain the sum of elements 1, 2, 3, and 4. Therefore, the Fenwick Tree for the above array would look like this:
To find the sum of a block of elements from N to M, you can take the sum of the first M and subtract the sum of the first N-1. To modify an element by adding X to it, we need to add X to it and all nodes that contain it within its range. For example, to update element 5, we need to update 5, 6, and 8. In general, if a node is updated, the smallest node not in its subtree needs to be updated. For example, to update 1, we update 1, which requires updating 2. 3 is in the subtree of 2, so we update 4. 5, 6, and 7 are in its subtree so we update 8.
Recall that something is in its subtree if it shares the same digits starting at and to the left of its LSB. Thus, the smallest number we can add to change that is the LSB itself - for example, to get the next value of 6 to be updated, since its LSB is 2, adding any value less than 2 will not change the digits to the left of an including 2, but adding 2 will set the place value of the LSB to a 0 instead of a 1, thus making it a value not in the subtree. So to update 5, we add the LSB, 1, and update 6. We add the LSB and update 8. If we had more values, we'd then update 16, then 32, etc. If we had 13 for example (1101), we'd add 1 and update 1110 = 14, then add 2 and update 10000 = 16.
For this challenge, you will not need to implement this.
In order to add the first N elements, we follow a reversed procedure. Recall that the value in each node is the sum of all elements between it and its parent (exclusive on the latter end). Thus, to add the first N elements, we take the value in N, which gives us the sum of the elements from N to M+1 (where M is its parent's index), then repeat this process to sum the first M elements. Then, the sum from 1 to M plus the sum from M+1 to N gives us the sum up to N.
Recall that a node B is in the subtree of A if it all digits up to A's LSB are the same. Thus, the minimum value we can subtract is B's LSB. This is because if we subtract a value less than the LSB, one of the trailing 0s in B will become a 1, and thus the new value will have a lower LSB than B and not share the appropriate digits. For example, subtracting 1 from 110 (6), the 0 becomes a 1 (101), and thus does not share the same first three digits. We can subtract 2, which removes the 1, and returns a value with a higher LSB, which means it matches the first 2 digits in this case.
In general, to sum the first N elements, if N is 0, we return 0; otherwise, we take the value in the Nth node, and then add the sum of the first N - LSB(N) elements.
The following pseudocode shows implementations of the modify and sum operations on a FT, both iteratively rather than recursively like I described.
func modify(index, change) # index points to the value in the represented array that you are modifying (1-indexed); change is the amount by which you are increasing that value
while index <= len(fenwick_tree)
fenwick_tree[index] += change
index += least_significant_bit(index)
func sum(count) # sum(n) sums the first n elements of the represented array
total = 0
while index > 0
total += fenwick_tree[index]
index -= least_significant_bit(index)
least_significant_bit(x) := x & -x
Given the Fenwick tree for an array
a and an integer
n, return the sum of the first
n values of
a; that is, implement the
sum function given as an example.
A reference implementation in Python for both the
sum functions is provided here.
These test cases are given 1-indexed, but you can accept a leading 0 to 0-index it if you would like.
[6, 6, 3, 20, 8, 12, 9, 24, 8, 12], 6 -> 32
[6, 4, 3, 36, 1, 8, 3, 16, 5, 4], 3 -> 7
[2, 10, 1, 4, 4, 2, 0, 32, 1, 14], 4 -> 4
[7, 8, 4, 36, 9, 0, 0, 8, 1, 4], 5 -> 45
[3, 0, 7, 12, 4, 18, 6, 64, 6, 14], 6 -> 30
[3, 4, 3, 28, 5, 6, 8, 40, 1, 8], 9 -> 41
[4, 8, 8, 4, 0, 18, 7, 64, 0, 12], 7 -> 29
[9, 0, 6, 16, 8, 14, 5, 64, 3, 18], 0 -> 0
[3, 14, 7, 12, 2, 6, 5, 0, 7, 18], 2 -> 14
- Standard Loopholes Apply
- This is code-golf, so the shortest answer in bytes in each language will be considered the winner of its language. No answer will be marked as accepted.
- You may take the two inputs in any order and the list in any reasonable format.
- You may assume that the integers in the tree are all non-negative.
- No input validation - the index will be non-negative and at most the length of the Fenwick tree
- You may assume that all values (in the list, as the index, and the output) will be at most 232-1
- Is my explanation of a Fenwick tree sufficient enough that most people can understand it?
- Are my test cases sufficient?
- Any more tag suggestions?