Via http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Introduction

We often need some sort of data structure to make our algorithms faster. In this article we will discuss the Binary Indexed Trees structure. According to Peter M. Fenwick, this structure was first used for data compression. Now it is often used for storing frequencies and manipulating cumulative frequency tables.

Let's define the following problem: We have n boxes. Possible queries are
1. add marble to box i
2. sum marbles from box k to box l

The naive solution has time complexity of O(1) for query 1 and O(n) for query 2. Suppose we make m queries. The worst case (when all queries are 2) has time complexity O(n * m). Using some data structure (i.e. RMQ) we can solve this problem with the worst case time complexity of O(m log n). Another approach is to use Binary Indexed Tree data structure, also with the worst time complexity O(m log n) — but Binary Indexed Trees are much easier to code, and require less memory space, than RMQ.

Notation

  BIT – Binary Indexed Tree
  MaxVal – maximum value which will have non-zero frequency
  f[i] – frequency of value with index i, i = 1 .. MaxVal
  c[i] – cumulative frequency for index i (f[1] + f[2] + … + f[i])
  tree[i] – sum of frequencies stored in BIT with index i (latter will be described what index means); sometimes we will write tree frequency instead sum of frequencies stored in BIT
  num¯ – complement of integer num (integer where each binary digit is inverted: 0 -> 1; 1 -> 0 )
NOTE: Often we put f[0] = 0, c[0] = 0, tree[0] = 0, so sometimes I will just ignore index 0.
 

Basic idea

Each integer can be represented as sum of powers of two. In the same way, cumulative frequency can be represented as sum of sets of subfrequencies. In our case, each set contains some successive number of non-overlapping frequencies.

idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx (look at the Table 1.1 for clarification). We also write that idx is responsible for indexes from (idx – 2^r + 1) to idx (note that responsibility is the key in our algorithm and is the way of manipulating the tree).

Image 1.3 – tree of responsibility for indexes (bar shows range of frequencies accumulated in top element)

Image 1.4 – tree with tree frequencies

Suppose we are looking for cumulative frequency of index 13 (for the first 13 elements). In binary notation, 13 is equal to 1101. Accordingly, we will calculate c[1101] = tree[1101] + tree[1100] + tree[1000] (more about this later).

Isolating the last digit
NOTE: Instead of "the last non-zero digit," it will write only "the last digit."

There are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.

Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have

-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b.

Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and -num:

           a1b
&      a¯1b
——————–
= (0…0)1(0…0)

继续阅读→