Fenwick Trees

July 20, 2018

There are some algorithms in coding theory where cumulative frequency tables must be maintained. This requires two tasks to be performed on an array of integers:

1) Calculate the cumulative sum of the first n elements of the array.

2) Modify the value of an element of the array.

One approach is to maintain an array of the elements, so that an element can be modified in O(1) time but calculating the cumulative sum requires O(n)time. Another approach is maintain an array of the cumulative sumes, so that a cumulative sum can be calculated in O(1) time but modifying a single element of the array takes O(n) time.

A Fenwick tree performs both operations in O(log n) time. The tree is normally embedded in a 1-based array, with the children of node i at nodes 2i and 2i + 1. Each element with index i a power of 2 contains the sum of the first i elements. Each element with index i a sum of two powers of 2 contains the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, found by clearing the least-significant bit in the index. Wikipedia has a good description of Fenwick trees.

For example, to find the sum of the first 1110 = 10112 items in the array, note that 11 has three bits set, so add elements 10002, 10102, and 10112. To modify the 11th element, modify 10112, 11002, 100002, and all higher powers of 2 up to the size of the array.

Your task is to implement Fenwick trees. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: