26
\$\begingroup\$

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:

image representation of a Fenwick tree in a flat array

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 , 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!

\$\endgroup\$
5
  • \$\begingroup\$ Sandbox (visible to 10k) \$\endgroup\$
    – hyper-neutrino
    May 13, 2021 at 23:41
  • 8
    \$\begingroup\$ Although this was presumably not the point of the post, this is the clearest explanation of FTs I've ever read. I'll bookmark it just for that purpose! \$\endgroup\$ May 14, 2021 at 9:03
  • \$\begingroup\$ btw, are Fenwick trees related to "segment trees"? Idk what the name of it is, but a data structure where there's a tree and each node represents the sum over a subarray, the leafs represent individual elements, and changes are propagated upward, so it is always possible to find a subarray sum in log n time. \$\endgroup\$
    – qwr
    May 16, 2021 at 6:10
  • \$\begingroup\$ @qwr They are called segment trees. Fenwick trees and segment trees are often used for the same task, specifically finding sums, but the crucial differences are that Fenwick trees / Binary Indexed Trees find the sum from x to y by taking 1..y minus 1..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\$
    – hyper-neutrino
    May 16, 2021 at 6:20
  • 1
    \$\begingroup\$ ... and can be used more generally. There's a good answer I found on SO here which says pretty much what I said here; basically, segtrees are slightly less efficient (by a constant factor) but BITs can only be used on invertible operations like sum or XOR, not stuff like max \$\endgroup\$
    – hyper-neutrino
    May 16, 2021 at 6:21

18 Answers 18

10
\$\begingroup\$

JavaScript (ES6), 24 bytes

Expects (array)(n), using the 1-indexed format.

a=>g=n=>n&&g(n&--n)+a[n]

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)
\$\endgroup\$
10
\$\begingroup\$

Jelly, 6 bytes

&’$Ƭị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! Or see the test-suite.

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
\$\endgroup\$
2
  • \$\begingroup\$ According to the rules, you can request a trailing 0, which would allow you to drop the . \$\endgroup\$
    – xigoi
    May 14, 2021 at 10:37
  • 1
    \$\begingroup\$ Thanks for notifying me of this relaxation in the specification @xigoi - I almost asked for that, but also wanted my bed at the time! \$\endgroup\$ May 14, 2021 at 11:21
7
\$\begingroup\$

Vyxal, 41 22 9 bytes

≬:‹⋏↔Ṫ‹İ∑

Try it Online!

-13 bytes thanks to Razetime.

\$\endgroup\$
4
  • \$\begingroup\$ -13: Try it Online! \$\endgroup\$
    – Razetime
    May 14, 2021 at 8:16
  • \$\begingroup\$ @Razetime Thanks! Wow I am bad at this. \$\endgroup\$
    – emanresu A
    May 14, 2021 at 8:44
  • 1
    \$\begingroup\$ Using golflangs efficiently takes a bit of time. Don't beat yourself up too much about it. \$\endgroup\$
    – Razetime
    May 14, 2021 at 9:18
  • \$\begingroup\$ @Razetime I mean, I only started a week ago... \$\endgroup\$
    – emanresu A
    May 14, 2021 at 9:19
7
\$\begingroup\$

J, 18 15 bytes

+/@:{~#:#]\&.#:

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use the option to always expect an extra, leading 0 and get rid of _1+ :) \$\endgroup\$ May 14, 2021 at 11:32
  • \$\begingroup\$ @JonathanAllan Thanks very much. \$\endgroup\$
    – Jonah
    May 14, 2021 at 14:21
6
\$\begingroup\$

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 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.
\$\endgroup\$
5
\$\begingroup\$

Husk, 8 bytes

ΣM!U¡Sn←

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Spec got relaxed to allow us to always expect a trailing 0 for 1-indexed solutions, which saves the h :) \$\endgroup\$ May 14, 2021 at 11:29
4
\$\begingroup\$

Stax, 8 bytes

ü→,¿(≡Y▓

Run and debug it

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
\$\endgroup\$
4
\$\begingroup\$

Python 3, 36 34 bytes

Saved 2 bytes thanks to the man himself Arnauld!!!

f=lambda a,n:n and a[n]+f(a,n&~-n)

Try it online!

Inputs Fenwick Tree \$a\$ (with a leading \$0\$) and \$1\$-indexed \$n\$.
Returns the sum to \$n^{\text{th}}\$ element.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Using the format with a leading 0 would save you 2 bytes. \$\endgroup\$
    – Arnauld
    May 14, 2021 at 9:31
  • \$\begingroup\$ @Arnauld Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    May 14, 2021 at 12:49
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Ruby, 31 bytes

f=->a,n{n>0?f[a,n&n-=1]+a[n]:0}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 31 38 36 bytes

Added 7 bytes to fix a problem kindly pointed out by Nick Kennedy and Arnauld.

f(a,n)int*a;{n=n?f(a,n--&n)+a[n]:0;}

Try it online!

Inputs a pointer \$a\$ to the Fenwick Tree and a \$1\$-based \$n\$.
Returns the sum to \$n^{\text{th}}\$ element.

\$\endgroup\$
0
3
\$\begingroup\$

Haskell, 48 bytes

import Data.Bits
a!n|n<1=0|y<-n-1=a!!n+a!(n.&.y)

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.

\$\endgroup\$
3
\$\begingroup\$

R, 49 bytes

f=function(a,n)"if"(n,f(a,bitwAnd(n,n-1))+a[n],0)

Try it online!

The same approach as @Arnauld's answer.

\$\endgroup\$
2
\$\begingroup\$

PowerShell, 61 bytes

function f($a,$n){for(;$n-gt0;$n=$n-band$n-1){$r+=$a[$n]};$r}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 11 bytes

Port of Arnauld's solution so be sure to +1 them.

©ßU&´U +UgV

Try it

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 19 17 bytes

IΣE⮌↨η²∧ι§θ&η±X²κ

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
  E                 Map over digits
        ι           Current digit
       ∧            Logical And
          θ         Input array `a`
         §          Indexed by
            η       Input integer `n`
           &        Bitwise And
               ²    Literal `2`
              X     Raised to power
                κ   Current index
             ±      Negated
 Σ                  Take the sum
I                   Cast to string
                    Implicitly print
\$\endgroup\$
2
\$\begingroup\$

MMIX, 4032 bytes (108 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
\$\endgroup\$
2
  • \$\begingroup\$ It should be possible to save a subtract and the if(!n) goto end logic if you say that input data must include the leading zero \$\endgroup\$
    – harold
    May 15, 2021 at 14:56
  • \$\begingroup\$ I was assuming it didn't. If it did, then swapping $2 and $0 throughout and changing POP 1,0 to POP 3,0 would save those. \$\endgroup\$ May 16, 2021 at 0:42
1
\$\begingroup\$

R, 40 bytes

function(a,n)sum(a,-a[n%%2^(0:n)-n])*!!n

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.

However, since negative indices in R 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.