[Question]
  [
## Background Information: What is a [Fenwick Tree](https://en.wikipedia.org/wiki/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:
[![image representation of a Fenwick tree in a flat array](https://i.stack.imgur.com/lHqao.png)](https://i.stack.imgur.com/lHqao.png)
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](https://tio.run/##bVHLbsMgEDybrxhFcmU3pMLKqVHdSz8jiiJUkwbFxhYmSvP1Lgs4stqe2GV2HizD3Z17s52mRp3QyYs6OqtUIa2V93LHspMyN/15QY29OOAZrTIJ9FhvoaENrDRfqqj4AsUaFfGz21m3yo@91QFNegGaxfcaG1QHrGsEcuppQtOlxhM2mmVWuas1SCzGKPJ47WZN7qM06pukXe9k6zMLNvsTgncI8o2oF374BzR5pqZOHLKm4mEf2Izpbuito6c3fcfY311UgpJEkTrNvdChjSsEx6vfYHgu7fY/GKR5XGiK0uej7/GM31/FssESc/UhR4W82cVVQo/IR47ASnWMRE3DaX@xXCFHoXmkRUIaDUPF4qIsy2n6AQ).
# 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](/questions/tagged/code-golf "show questions tagged '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!
  
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
&’$ƬịS
```
A dyadic Link that accepts \$N\$ on the left and the Fenwick Tree (using the trailing `0` option) on the right and yields the prefix sum.
**[Try it online!](https://tio.run/##y0rNyan8/1/tUcNMlWNrHu7uDv7//7/Z/2gzHQUgMtZRMDLQUbDQUTA00lGwBPJM4DyDWAA "Jelly – Try It Online")** Or see the [test-suite](https://tio.run/##RY@9DcIwEEb7TOECUVnC/3Y6dqCMXNKgLECHaJmACWjYgBKJPcgi5vydHSRLyfnefX53Os7zuZTtcrlvPs/v63Yo78d@t1yfpUzTFKSgY6UwSookhTZSjFS5tVKZkDxIsA6spT8NgApNhUenkhYkjWkFxuHUGOoZXOmGOqAROY5DR3DNZM30AC0akaWooxPUg8Onh4bOsqlJkAv8iOralRxB8p5soDg0cqj6rx@BslzgjRM/6Zm1PFlZ1QVqu9kajPl1gYaaPOQf "Jelly – Try It Online").
### How?
```
&’$ƬịS - Link: N, FT
   Ƭ   - start with k=N and collect up while distinct applying:
  $    -   last two links as a monad - f(k):
 ’     -     decrement (k)
&      -     (k) bitwise AND (k-1)
    ị  - index into (FT)
     S - sum
```
[Answer]
# JavaScript (ES6), 24 bytes
Expects `(array)(n)`, using the 1-indexed format.
```
a=>g=n=>n&&g(n&--n)+a[n]
```
[Try it online!](https://tio.run/##bZDNasMwEITvfYo9mRW1G/1Zsg/OiwQfTJqYliCXpvT13dWuyEENCKyx9Glm9nP5Xe7n74@vny5t75f9Ou3LdFynNB1T06yYmq5L6nU5pXk/b@m@3S5vt23FK55CC7RcC1a3MLRgbAsjKV/UrDAoBYcDOPvyn/XMOtoZBkgYEj2dzAoAnbCxRsnFaIY8L9IkneVfJrPoBfU1GtnIi@vIXIleTAH7gvY16/hulJr0hBm4fvD8yb6PtvoJK23twAWD5JAWA7cdi6@pWZmmxNZiG8VWy5ABo7B2rFmpGGSwuaYXewljyBm1sM8i59ulr@VX@scIcma0ghq//wE "JavaScript (Node.js) – Try It Online")
### Commented
```
a =>         // outer function taking the array a[]
g = n =>     // inner recursive function taking n
  n &&       // stop if n = 0
  g(n & --n) // otherwise: do a recursive call where n AND n - 1 is passed,
             // which clears the LSB (e.g. 0b110 & 0b101 -> 0b100)
  + a[n]     // add a[n] to the final sum (where n was decremented above)
```
[Answer]
# [J](http://jsoftware.com/), 18 15 bytes
```
+/@:{~#:#]\&.#:
```
[Try it online!](https://tio.run/##NZDLSsRAEEX3fsXFgOPgGLuqK52kYWBgwJUr185KHMSNHyD465m6/aBJaMjh1Kn8bPfj7opjxg4HBGR/nkec399et6eXU/77H/Jw@XgYh7ztcff1@f2LqDjiMSD5idCABaJYoVZue1z9Q0XnTpqTMUGciJCECUYuNs4qp5DgjPlRD/FBAimgdXCq5Owio3F1rhRU4dQbQ@UiyHqeQRYWm7@qsjeadJSRurgj0c6SheDaQF0ryDU5PVA5Uxna2nMj23C2JW7reUYtB0hxhkaK9eF@K6EK/p1SXUjFdgM "J – Try It Online")
-3 thanks to Jonathan Allan for pointing out that I could take the lists with an extra 0 in front
Consider index 6:
* `]\&.#:` Prefixes "under" conversion to binary. Since 6 is `1 1 0`, its prefixes,
including 0 fill on the right, are:
```
1 0 0
1 1 0
1 1 0
```
And after "under" converts back to decimal we get:
```
4 6 6
```
* `#:#` Filter by the binary number:
```
1 1 0 # 4 6 6
  becomes:
4 6
```
* `+/@:{~` Select `4 6` from the list we're given and sum.
[Answer]
# [Vyxal](https://github.com/Lyxal/Vyxal), ~~41~~ ~~22~~ 9 bytes
```
≬:‹⋏↔Ṫ‹İ∑
```
[Try it Online!](http://lyxal.pythonanywhere.com?flags=&code=%E2%86%92f%7B%3A%7C%3A%E2%86%90f%24i%C2%A5%2B%C2%A3%3A%3A0%24-%E2%8B%8F-%7D%C2%A5&inputs=%5B0%2C%206%2C%204%2C%203%2C%2036%2C%201%2C%208%2C%203%2C%2016%2C%205%2C%204%5D%0A3&header=&footer=)
-13 bytes thanks to Razetime.
[Answer]
# x64 (Windows), 13 bytes
```
31 c0
03 04 8a
c4 e2 70 f3 c9
75 f6
c3
```
In assembly:
```
    xor eax, eax
_sumloop:
    add eax, [rdx + rcx*4]
    blsr ecx, ecx
    jnz _sumloop
    ret
```
Takes the address of the FT in `rdx` and the index in `ecx`. The FT must have a zero stored as its zeroth element, to ensure that passing zero as index returns zero (it doesn't affect anything else, the only way in which the zeroth entry is used is if the index is zero to begin with, otherwise when it becomes zero the loop stops).
[blsr](https://www.felixcloutier.com/x86/blsr) directly implements "reset lowest set bit", and sets the zero flag according to the result, which we can then branch on.
Fun facts:
* `blsr` weighs in at a gigantic 5 bytes, which does not save space compared to a `lea \ and` pair .. but there is more to it. In any case `blsr` seemed like more fun. The fun thing is, in order to use `lea \ and`, we'd need an extra register, and on Windows we'd be forced to either pick a non-volatile register (adding size for save/restore) or one of the "numbered registers" (which would cost two extra REX prefixes to encode). However, switching to the SysV x64 calling convention would work around that, since it uses `rdi` and `rsi` for the first two parameters and that frees up `rdx` or `rcx` as a scratch register.
* `loop` (with its built-in `dec rcx`) seemed useful, but isn't, since we need the value from before the decrement as well and recreating it cancels the size benefit that `loop` might have had.
* can be adapted at no addition cost to deal with an FT with over 232 entries, but adapting it to deal with results of 232 are greater would cost an extra byte (`REX.W` on the `add`, the `xor` can stay the same). Adapting the `lea \ and` version for giant FTs would cost additional `REX.W` bytes, but for `blsr` the `W` bit is already present in the VEX-prefix so it doesn't cost extra space.
[Answer]
# [Husk](https://github.com/barbuz/Husk), 8 bytes
```
ΣM!U¡Sn←
```
[Try it online!](https://tio.run/##yygtzv7//9xiX8XQQwuD8x61Tfj//7/Z/2gzHTMdYx0jAx0LHUMjHUsdIxMIyyAWAA "Husk – Try It Online")
There may be a way to shorten with `ṁ` here. Not sure how, though.
## Explanation
```
ΣM!hU¡Sn←
     ¡    infinite list using n:
      S    Self
       n   bitwise AND with
        ←  its decrement
    U     keep all unique results
   h      remove last
 M!       map left(indices) to indexes in right(fenwick tree)
Σ         sum
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 8 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
ü→,¿(≡Y▓
```
[Run and debug it](https://staxlang.xyz/#p=811a2ca828f059b2&i=%5B0,+6,+6,+3,+20,+8,+12,+9,+24,+8,+12%5D,+6+%0A%5B0,+6,+4,+3,+36,+1,+8,+3,+16,+5,+4%5D,+3+%0A%5B0,+2,+10,+1,+4,+4,+2,+0,+32,+1,+14%5D,+4+%0A%5B0,+7,+8,+4,+36,+9,+0,+0,+8,+1,+4%5D,+5+%0A%5B0,+3,+0,+7,+12,+4,+18,+6,+64,+6,+14%5D,+6+%0A%5B0,+3,+4,+3,+28,+5,+6,+8,+40,+1,+8%5D,+9+%0A%5B0,+4,+8,+8,+4,+0,+18,+7,+64,+0,+12%5D,+7+%0A%5B0,+9,+0,+6,+16,+8,+14,+5,+64,+3,+18%5D,+0+%0A%5B0,+3,+14,+7,+12,+2,+6,+5,+0,+7,+18%5D,+2+&m=2)
Takes inputs with a leading 0 for 0-indexing.
## Explanation
```
{cvIgi@|+
{   gi    generate values from n, till invariant:
 c         copy
  v        decrement
   I       bitwise AND
      @    get elements at those indexes in a
       |+  sum
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), 31 bytes
```
f=->a,n{n>0?f[a,n&n-=1]+a[n]:0}
```
[Try it online!](https://tio.run/##PVBBCsIwELz3FYGCWEwhm8Q0FVofEoJUsMcgWg8ivr1udlMh0MzOZGa2j9f1va7z0I6TTJ80qvMc8LZL7QDxMIUUT@q73sUcgpMCj5FCKym8FKCl6BHZgiLysdqklqQGb0A8AkBwRAaFJlZ1wPegiLd0ECM0mkaQZaGjt5aNeuJLOPsEQ4OO26AOPLV0lj6wabiN9lTAsSlH@6zgFThJsUnHJqpsFjjc8Ra5gGUvdgZfgvK4tNEkP/4L@thU9XJ7LpckBrHnf2m3Rj2JUKqb9Qc "Ruby – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/3/), ~~36~~ 34 bytes
Saved 2 bytes thanks to the man himself [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld)!!!
```
f=lambda a,n:n and a[n]+f(a,n&~-n)
```
[Try it online!](https://tio.run/##PVHRboMwDHznK/w0iJpKJKRAK7EfYWhKaVCrbSkqTNqG2K8zx4ahSOTsy93F6b/H691ny9JV7/bjfLFgpT95sP4CtvbNrkuw8PS792IZ3TC@WqggqXMJuDIJOpVQSlBawhGRWVEjIXAMcTLcKWogUAgO2AkMPKRS6hlaiBFmmkqKKAWdMyxypP7quGpkVCg4AvJUSdFyQz@1cTiJLsk8Z1G2LgODc7NTyiIFi6Tbddg85xuEAIa1WFmVq1Eor2k00Q//ActGRDRDH2bI8zNboCNxkKlF5L56147uEmhhGgUPCIkZEgyG1pxGGRG1V9e@uUfgxi@fujBtLIF2KotF1N0f4Umlg5uHn1uf8CtK4CQSNjNxigC/MwrVaQM7sIQHxF1yll4Q7B83PyZdPNlZwuRn2D/DNMwwrTFqV1VDM8di@QM "Python 3 – Try It Online")
Inputs Fenwick Tree \$a\$ (with a leading \$0\$) and \$1\$-indexed \$n\$.  
Returns the sum to \$n^{\text{th}}\$ element.
[Answer]
# Java, ~~49~~ ~~47~~ 35 bytes
```
a->n->{for(;n>0;n&=n-1)a[0]+=a[n];}
```
Expects array with leading zero and sets the first element of the input array to the sum.
[Try it online!](https://tio.run/##dVDBSsNAED3br5iTJLpZmraKkjYXQfDgqceQw5puytZkEnYnlRLy7XGyDYKIwx72zZt57zEndVbR6fA5mrptLMGJsezIVLLssCDToLxLFn9I7rXdR2UKKCrlHLwrg9AvgMuRIu6/zutbg5Tl4qVB19Xabt@Q9FHbNC13o4pSjNK@bGyQYLpM8HaHURyqbJnf71SGeTKMiRedzWbtc2MOULNlsCdr8JjloOzRhf3ihrSjAPUXeNt@KeDRv7WAFYMnAfFKwDOjzYwG5sPkn82N31zzL/bjDGIGD8wMYh1eww3XiNacFelfGb2m1@OAVkzSgOH1TlOVUrVtdQmYDKUqCt1yhCnM/uJI17LpSLIuUoXTDN/lx3IYvwE)
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~31~~ ~~38~~ 36 bytes
Added 7 bytes to fix a problem kindly pointed out by [Nick Kennedy](https://codegolf.stackexchange.com/users/42248/nick-kennedy) and [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld).
```
f(a,n)int*a;{n=n?f(a,n--&n)+a[n]:0;}
```
[Try it online!](https://tio.run/##bVRtb5tADP6eX2EhZYLk0OA4XlKa9cO0X5GgCRHSorJrFSItWsRfX@azgXJZI4Kxn@exfWe4yn@uqtvt6JZCe40@r8r8qrf6iQK@/0V763Kni4cg72/vJyS4RBKABloPrnB8O4EJQgNbCHI0j9DmsF43HpDi6DrLbnlwhNs8OQKcB8fxBJS7pvBy6BdG@qtstOstrgvAnwmc6@4c7ArMeE0E4BUJkIGATEAoBWzQU4PX55MinBSKFBE@hURDJ0QnRmTGl8zHhGFATEUX@uhGkkLhXBCxIKWcigtsiD30ZudXTI8ITrl1VIUZLSlRZKwC8aTgFciMmk64IDeZzfgJ83kvuKeAC6RcILjbopQF3HTCu2IaV1yHq4bzEtnUkiENq5AkjqeFoWCc3YpUHatojoKHw0ayidgoNjGbhE3KZpaT/J8t5@yaP/Xb0aXU3tfBW7ErYIaGNhraqLRRaaORjUY2qmxU2Whso7GNJjaa2Ghqo6mNZjaaefdbpKcvgF8hfnc2NCScg5zx68t7XZ3rwzBeSRzzAaAmQq7CgUl@T8wrSrrqpTyt8F5Xr/UJhWCkzv7yQ@4vm@/4j80HPvMjZ1B@nBL6UF@Gk4IeH8cFjg19rHGK0HFi2HjgULpxERozDQsnvMjn8Koc4O4zFNpR3H4KdwjzuWjHa4xPm3cvHE@8nePdBTETHpj/MwsBywP438x92e017qDGoYtpm@vttisGYb/ob3@rY1s@dzf/9z8 "C (gcc) – Try It Online")
Inputs a pointer \$a\$ to the Fenwick Tree and a \$1\$-based \$n\$.  
Returns the sum to \$n^{\text{th}}\$ element.
[Answer]
# [Haskell](https://www.haskell.org/), 48 bytes
```
import Data.Bits
a!n|n<1=0|y<-n-1=a!!n+a!(n.&.y)
```
[Try it online!](https://tio.run/##PY/PaoQwEIfveYoIS1dptEmM/7qmh9Jj30D2EFjbhrpR1MMu7LvbyUQKAZ3Ml99882OW334Yts1ep3Fe6YdZTfZu14WYyD1cKzR/3NvUpUKbKHLPJopd9pTdk@1qrNOXkdDYsjFp06@rmeLLPE40T7JlMi5@0cf0mLSHt@9@/bSuJ3To1y42hjmXnPXcm8tC7clo/mrMyeHFYTV2oM6dblhSyJ9m69YYdLS@MXjLbgmhfvrWlYzCyRmVnNGaUSEZbaBSe3WGPk3faC6JZxWyOfwJBKAQUBTQATL3ZEU6yBAcEYUHaihziVfCk8qTinQVpqgQ2SC2e4TEArmCdDk2qiAIvKhRvFT4wczgyZENnrJGtTIMCUY1kA2mCtKFLYMBD6FVCOX78pVHZUO6IFeGfb2gCtlhkvCx3LNhvu/ushJfFf/@npSeFOoP "Haskell – Try It Online")
The relevant function is `(!)`, which takes the Fenwick tree `a` as a list of integers with a leading 0 and `n` as a 0-indexed integer.
Haskell is probably the only language which needs an import to perform bitwise operations.
[Answer]
# [R](https://www.r-project.org/), 49 bytes
```
f=function(a,n)"if"(n,f(a,bitwAnd(n,n-1))+a[n],0)
```
[Try it online!](https://tio.run/##K/r/P802rTQvuSQzP08jUSdPUykzTUkjTycNyEnKLCl3zEsB8vJ0DTU1tROj82J1DDT/p2kka5jpKACRsY6CkYGOgoWOgqGRjoIlkGcC5WkC5TW5iFQJNBMA "R – Try It Online")
The same approach as [@Arnauld's answer](https://codegolf.stackexchange.com/a/225635/55372).
[Answer]
# [PowerShell](https://github.com/TryItOnline/TioSetup/wiki/Powershell), 61 bytes
```
function f($a,$n){for(;$n-gt0;$n=$n-band$n-1){$r+=$a[$n]};$r}
```
[Try it online!](https://tio.run/##DcZBCsIwEEbhvaeYxb9IcAqtVqmUgPcQF6M2KpSJpBUXpWePs3nv@6TfkKfXMI4FEs5uz9QyWXcd04HpyGRoa6bG5DfQcCrxq/f5nZSigzDULzFl10Or51zbgukm@rA1fkHeBsgFel175LVEghC0/AE "PowerShell – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 11 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Port of [Arnauld's solution](https://codegolf.stackexchange.com/a/225635/58974) so be sure to +1 them.
```
©ßU&´U +UgV
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=qd9VJrRVICtVZ1Y&input=NgpbNiwgNiwgMywgMjAsIDgsIDEyLCA5LCAyNCwgOCwgMTJd)
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~19~~ 17 bytes
```
ＩΣＥ⮌↨η²∧ι§θ＆η±Ｘ²κ
```
[Try it online!](https://tio.run/##NYrNCsIwEIRfZY8bWKHWfzzZnjwoRY@lh6VdbLBNNYmtbx@j4DDMwDdTt2zrgbsQCquNx5ydx@urxxM/8CKjWCeYcYyWIFWK4GAa1LH80TTyxidBpv2knXyHeDrLjb1gMUxiMSW4q7/2IZRlQrAh2BIsCRZrgh1B8nNE80grglUVZmP3AQ "Charcoal – Try It Online") Link is to verbose version of code. 0-indexed. Explanation: Turns out to work somewhat like Jonah's J answer, but having to use bit twiddling instead of that handy zero-filled prefixes function.
```
     η              Input integer `n`
    ↨ ²             Converted to base 2
   ⮌                Reversed
  Ｅ                 Map over digits
        ι           Current digit
       ∧            Logical And
          θ         Input array `a`
         §          Indexed by
            η       Input integer `n`
           ＆        Bitwise And
               ²    Literal `2`
              Ｘ     Raised to power
                κ   Current index
             ±      Negated
 Σ                  Take the sum
Ｉ                   Cast to string
                    Implicitly print
```
[Answer]
# MMIX, ~~40~~32 bytes (~~10~~8 instrs)
Assumes array of octas, preceded by 0 octa, which first argument points to.
(jxd)
```
00000000: e302 0000 3b01 0103 8eff 0001 2202 02ff  ẉ£¡¡;¢¢¤⁾”¡¢"££”
00000010: 27ff 0101 c801 01ff 5b01 fffc f803 0000  '”¢¢Ṁ¢¢”[¢”‘ẏ¤¡¡
```
```
sfen    SET  $2,0           // s = 0
        SLU  $1,$1,3
0H      LDOU $255,$0,$1
        ADDU $2,$2,$255     // loop: s += a[n]
        SUBU $255,$1,$1
        AND  $1,$1,$255     // n &= n - 1
        PBNZ $1,0B          // if(n) goto loop
        POP  3,0            // return s
```
---
Old version:
Assumes the tree is an array of octas.
(jxd)
```
00000000: 27020008 e3000000 3b010103 42010006  '£¡®ẉ¡¡¡;¢¢¤B¢¡©
00000010: 8fff0102 220000ff 27ff0101 c80101ff  Ɓ”¢£"¡¡”'”¢¢Ṁ¢¢”
00000020: 5b00fffc f8010000                    [¡”‘ẏ¢¡¡
```
```
sfen    SUBU $2,$0,8        // a = arr - 1
        SET  $0,0           // s = 0
        SLU  $1,$1,3
        BZ   $1,1F          // if(!n) goto end
0H      LDOU $255,$1,$2
        ADDU $0,$0,$255     // loop: s += a[n]
        SUBU $255,$1,$1
        AND  $1,$1,$255     // n &= n - 1
        PBNZ $1,0B          // if(!n) goto loop 
1H      POP   1,0           // end: return s
```
[Answer]
# [R](https://www.r-project.org/), 40 bytes
```
function(a,n)sum(a,-a[n%%2^(0:n)-n])*!!n
```
[Try it online!](https://tio.run/##bZDxSsMwEMb/31NkyKCRFHKXa9MK@iKiMoqDMcxgOnz8erlrqmRCIPmS/O677y7z4T19H6fT2@f143E@XNP0dTynZu@S5Rve2/1z2u3wtfEPybbpxd5vt@kv1UxN7wyv4Ax6ZwZnAJ0ZWdGiLL8ba@5M@2QCbm5gEjjwCYRgASw6fmE0FDRWJLuAF4ZksWYZUK4go1RQqtAoPqSmo3BL6@rZrWBXkUF@Rg3JBWCQ8D3JJq6/Wf0trFlxkHi9tqEhBkbH1RcqVGepTXu1jWrrlxHHwuJYsRqw16nmkKTu2gtkY1/gf1rO35fAKGW6dQYZxYICbeYf "R – Try It Online")
Non-recursive approach: the unique values of `n-n%%2^(0:n)` give the indices that we need to sum.
We could use `sum(a[unique(n-n%%2^(0:n))])` for [41 bytes](https://tio.run/##bZD9asQgEMT/v6dYKAcKHuhqYlJoX6TclSPcQSi13Efo46frbkyLVxCSUX/OzF7n8yl9j8PH@236fJnPUxru41dSR5M07ajj25TGy3RSaZe2Wzwo@5y03uu/mBpUa4CWN4DWQGfAoYGeVFiUpnPQ8AS7V/C4eYADw57@HBMkHImGTgj1BY0VSS7OMhN4kSbpkbdcRkNBQ4VG9gli2jO3RBfPZgWbivR8M0pJesB1XL4N/GHX3672EZau2HG9VmJIiY7QfvV1FSqzlNBWbKPY2mXEsbDYV6wUbGWquWQQd8nisrEt8D@R8/WlMPIzzTqDjGJBXdjMPw).
However, since negative indices in [R](https://www.r-project.org/) specify elements to *exclude*, they're effectively used uniquely already, so we can subtract the sum of the elements of `a` that we *don't* want (`a[n%%2^(0:n)-n]`) from the sum of `a` to get the same answer saving one byte.  
This unfortunately fails when `n` equals zero, so we need to multiply the result by zero in this case (or by 1 otherwise), hence the ugly `*!!n` at the end.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 9 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
Dλ£D<&}èO
```
[Try it online](https://tio.run/##yy9OTMpM/f/f5dzuQ4tdbNRqD6/w///fjCvaQMcMCI11jAx0LHQMjXQsdYxMwKxYAA) or [verify all test cases](https://tio.run/##NY89CsIwGIavUjo4vUN@vqYtCF26e4BQUMHByaEgdHD1AF7BxTu46e4hvEj93qQSCEme7/3Jadztj4f5PHVl8b3eirKbtuPcf56ve79eXd6PzYw5xoBoEHR5OIMG1qGFk3QaBhTR5wHRAR9gFXjYgAqSsBA7WKNIdDkYeL3DZl6R16oSylulKWVRp3QPTmiwwDbsIrot8jYPMN01GhroxKwm4ZqYZelvKK8pN//yhpyhgZ01V@hBN5sNXPbX99TAgT9LdZQPPw).
### [05AB1E (legacy)](https://github.com/Adriandmen/05AB1E/tree/fb4a2ce2bce6660e1a680a74dd61b72c945e6c3b), 9 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
bη0ζζCÙèO
```
Port of [*@Jonah*'s J answer](https://codegolf.stackexchange.com/a/225644/52210), so make sure to upvote him as well!
[Try it online](https://tio.run/##MzBNTDJM/f8/6dx2g3Pbzm1zPjzz8Ar////NuKINdMyA0FjHyEDHQsfQSMdSx8gEzIoFAA) or [verify all test cases](https://tio.run/##NY89CsIwGIavUjo4vUN@vqYtCF26e4BQUMHByaEgdHD1AF7BxTu46e4hvEj93qQSCEme7/3Jadztj4f5PHVl8b3eirKbtuPcf56ve79eXd6PzYw5xoBoEHR5OIMG1qGFk3QaBhTR5wHRAR9gFXjYgAqSsBA7WKNIdDkYeL3DZl6R16oSylulKWVRp3QPTmiwwDbsIrot8jYPMN01GhroxKwm4ZqYZelvKK8pN//yhpyhgZ01V@hBN5sNXPbX99TAgT9LdZQPPw).
Both take the inputs in the order \$n,a\$, and are 0-based with the additional leading `0` in \$a\$.
**Explanation:**
```
 λ        # Start a recursive environment,
D £       # to output the first (implicit) input amount of values
D         # Starting with a(0) = the first (implicit) input
          # Where every following a(n) is calculated as:
          #  (implicitly push the previous term a(n-1))
   D      #  Duplicate this a(n-1)
    <     #  Decrease the copy by 1
     &    #  Bitwise-AND the a(n-1) and a(n-1)-1 together
 }        # After the recursive environment:
  è       # 0-based index each value into the second (implicit) input-list
   O      # And sum those together
          # (which is output implicitly as result)
```
```
b         # Convert the (implicit) input-integer to a binary-string
 η        # Get the prefixes of this string
  0ζζ     # Pad each with trailing 0s until the list of strings is rectangular-shaped:
   ζ      #  Zip/transpose; swapping rows/columns,
  0       #  using a "0" as filler for unequal length rows
    ζ     #  Then zip/transpose back
     C    # Convert each string back to an integer
      Ù   # Uniquify it
       è  # 0-based index each value into the second (implicit) input-list
        O # And sum those together
          # (which is output implicitly as result)
```
Note: the legacy version didn't had the recursive environment `λ` yet, so the first program only works in the new version of 05AB1E. Also, zip/transpose doesn't work with a list of strings in the new version, so the second program only works in the legacy version of 05AB1E - and would require an additional `S` (split to characters/digits) and `J` (join together) for the new version of 05AB1E: `bSη0ζζJCÙèO` - [try it online](https://tio.run/##yy9OTMpM/f8/KfjcdoNz285t83I@PPPwCv///824og10zIDQWMfIQMdCx9BIx1LHyATMigUA).
]