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.

Advertisements

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)
      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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: