## Fenwick Trees

### July 20, 2018

The article by Fenwick gives source code in Pascal, and the Wikipedia article gives source code in C, so our task is easy:

`(define size 100)`
`(define fen (make-vector (+ size 1) 0))`
`(define (lsb i) (bitwise-and i (- i)))`
```(define (incr i k) ; add k to element at index i
(do ((i i (+ i (lsb i))))
((< size i))
(vector-set! fen i (+ (vector-ref fen i) k))))```
```(define (sum i) ; cumulative sum through index i
(let loop ((i i) (sum 0))
(if (zero? i) sum
(loop (- i (lsb i))
(+ sum (vector-ref fen i))))))```

As an example, we compute the cumulative sum of the integers to n:

```> (do ((n 1 (+ n 1))) (( fen
#(0 1 3 3 10 5 11 7 36 9 19 11 42 13 27 15 136 17 35 19 74 21
43 23 164 25 51 27 106 29 59 31 528 33 67 35 138 37 75 39
292 41 83 43 170 45 91 47 648 49 99 51 202 53 107 55 420 57
115 59 234 61 123 63 2080 65 131 67 266 69 139 71 548 73 147
75 298 77 155 79 1160 81 163 83 330 85 171 87 676 89 179 91
362 93 187 95 2576 97 195 99 394)```

The sum 2080 is at index 64 of the array. The values in the array look odd, but by taking appropriate sums they properly compute the cumulative sum:

```> (sum 100)
5050```

We test by comparing the sum produced by the Fenwick tree to the formula for the sum of the first n integers due to Gauss; in the `assert`, no news is good news:

`(define (gauss n) (* n (+ n 1) 1/2))`
```> (do ((n 1 (+ n 1))) ((< 100 n))
(assert (sum n) (gauss n)))```

You can run the program at https://ideone.com/gxrptN.

Pages: 1 2

### One Response to “Fenwick Trees”

1. Daniel said

Here’s a solution in Python.

```# Binary indexed tree (Fenwick Tree)
class BIT(object):
# Initializes n frequencies to zero
def __init__(self, n):
self._n = n
self._v = [0] * n

# Returns sum of first i elements
def sum(self, i):
_sum = 0
while i > 0:
_sum += self._v[i-1]
i &= i - 1
return _sum

# Adds k to i'th element (0-indexed)
i += 1
while i <= self._n:
self._v[i-1] += k
i += i & -i

# Initialize in O(n) with specified frequencies in f
def init(self, f):
for i in range(self._n):
self._v[i] = f[i]
for i in range(1, self._n + 1):
j = i + (i & -i)
if j <= self._n:
self._v[j-1] += self._v[i-1]

if __name__ == "__main__":
n = 100
bit = BIT(n)
# Initialize one element at a time. O(n log n)
for x in range(n):