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.
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) def add(self, i, k): 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): bit.add(x, x+1) for x in range(1, n+1): assert ((x * (1 + x)) / 2) == bit.sum(x) # Initialize all at once. O(n) f = [x for x in range(1, n + 1)] bit.init(f) for x in range(1, n+1): assert ((x * (1 + x)) / 2) == bit.sum(x)