Background Information: What is a Fenwick Tree?
With a normal array, it costs \$O(1)\$ to access and modify an element, but \$O(n)\$ to sum \$n\$ elements. Working with a prefix sum array (an array where the \$i\$th value represents the sum of the first \$i\$ values in the underlying data), access and summation are \$O(1)\$, but modification is \$O(n)\$. Thus, if you want to do a large amount of both, you will need a different data structure.
A Fenwick Tree is one such data structure that can solve this problem. The following diagram will help with the understanding:
Don't worry too much about the "tree" part of it. This looks like a flat array but it does represent a tree (and probably not in the sense the image makes it look like) - if you're curious about the tree part, I would recommend checking out the Wikipedia page, but it's a bit much for me to explain here.
This image shows what each value in the FT represents. For example, the 12th element of the FT is the sum of the 9th to 12th elements. The 8th element of the FT is the sum of the first 8. The 16th is the sum of all 16 values.
Note that the \$N\$th value represents the sum of the \$k+1\$th value to the \$N\$th value, where \$k\$ is the number you get when you flip the least significant bit of \$N\$ (the rightmost bit that is turned on). For example, 12 is 1100 in binary, so removing its LSB gives 1000, which is 8.
Now, the above logic lets us get both our summation (and by extension, access) and modification operations to \$O(\log N)\$, which is individually worse than both normal and prefix-sum arrays, but combined, is a more efficient data structure if you need to do both operations a lot.
To sum the first \$N\$ elements, we start with FT[N]. This gives us the sum from \$k+1\$ to \$N\$. Thus, the sum of the first \$N\$ elements is FT[N] plus the sum of the first \$k\$ elements. We get \$k\$ by subtracting the least significant bit from \$N\$. Eventually, we reach a number like 8, and subtracting the LSB gives 0, so we stop at 0.
The next part is about modifying a FT. This isn't required for this challenge, so feel free to skip it, but it's cool if you're interested.
To modify the \$N\$th element (as in increasing it by a certain value) we start by modifying FT[N], which clearly needs to be updated. The next value to be updated is actually very simple to find.
Observing the diagram, if we modify 12, note that we don't want to modify 13, 14, or 15. This is because they don't contain the 12th element in their summation range. We know this because by removing the LSB of any of those numbers repeatedly, we will eventually get 12. Thus, we want the first number that doesn't contain the non-trailing-zero-digits of 12 as a prefix. In this case, 12 is 1100, so we need a number that doesn't look like 11__.
The smallest number satisfying this condition is obtained by adding the LSB. Adding any smaller value would just fill in the trailing zeroes of the original number; adding the LSB changes the bit in the position of the LSB from a 1 to a 0, which gives the smallest number that doesn't share the prefix.
Therefore, if we want to update element 9, we first update 9, then the LSB of 9 is 1, so we update 9+1=10. Then, the LSB of 10 is 2, so we update 10+2=12. Then, the LSB of 12 is 4, so we update 12+4=16. Then, we would update 32, but that value is now out of range, so we stop here.
The following pseudocode shows implementations of the modify and sum operations on a FT iteratively.
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
Challenge
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.
Reference Implementation
A reference implementation in Python for both the make_tree and sum functions is provided here.
Test Cases
These test cases are given 1-indexed, but you can accept a leading 0 to 0-index it if you would like. You may also request a trailing 0 to be included (though adding a trailing 0 should not break any solutions that do not request this).
[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
Rules
- 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 \$2^{32}-1\$
Happy Golfing!
xtoyby taking1..yminus1..x, which only works because addition has an inverse - if you wanted to be able to query the max of a range, you would need a segment tree, since there is no inverse operator to max. BITs take half as much memory and have a smaller constant factor even though both are log N, but segment trees are easier to implement (I think)... \$\endgroup\$