
Introduction Notation Basic idea Isolating the last digit Read cumulative frequency Change frequency at some position and update tree Read the actual frequency at a position Scaling the entire tree by a constant factor Find index with given cumulative frequency 2D BIT Sample problem Conclusion References Introduction Let's define the following problem: We have n boxes. Possible queries are 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 Basic idea 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).
Table 1.1
Table 1.2  table of responsibility 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 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. Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and num: a1b Read cumulative frequency int read(int idx){ int sum = 0; while (idx > 0){ sum += tree[idx]; idx = (idx & idx); } return sum; } Example for idx = 13; sum = 0:
Image 1.5  arrows show path from index to zero which we use to get sum (image shows example for index 13) So, our result is 26. The number of iterations in this function is number if bits in idx, which is at most log MaxVal. Time complexity: O(log MaxVal). Change frequency at some position and update tree void update(int idx ,int val){ while (idx <= MaxVal){ tree[idx] += val; idx += (idx & idx); } } Let's show example for idx = 5:
Image 1.6  Updating tree (in brackets are tree frequencies before updating); arrows show path while we update tree from index to MaxVal (image shows example for index 5) Using algorithm from above or following arrows shown in Image 1.6 we can update BIT. Time complexity: O(log MaxVal). Read the actual frequency at a position Probably everyone can see that the actual frequency at a position idx can be calculated by calling function read twice  f[idx] = read(idx)  read(idx  1)  just by taking the difference of two adjacent cumulative frequencies. This procedure always works in 2 * O(log n) time. If we write a new function, we can get a bit faster algorithm, with smaller const. If two paths from two indexes to root have the same part of path, then we can calculate the sum until the paths meet, substract stored sums and we get a sum of frequencies between that two indexes. It is pretty simple to calculate sum of frequencies between adjacent indexes, or read the actual frequency at a given index. Mark given index with x, its predecessor with y. We can represent (binary notation) y as a0b, where b consists of all ones. Then, x will be a1b¯ (note that b¯ consists all zeros). Using our algorithm for getting sum of some index, let it be x, in first iteration we remove the last digit, so after the first iteration x will be a0b¯, mark a new value with z. Repeat the same process with y. Using our function for reading sum we will remove the last digits from the number (one by one). After several steps, our y will become (just to remind, it was a0b) a0b¯, which is the same as z. Now, we can write our algorithm. Note that the only exception is when x is equal to 0. Function in C++: int readSingle(int idx){ int sum = tree[idx]; // sum will be decreased if (idx > 0){ // special case int z = idx  (idx & idx); // make z first idx; // idx is no important any more, so instead y, you can use idx while (idx != z){ // at some iteration idx (y) will become z sum = tree[idx]; // substruct tree frequency which is between y and "the same path" idx = (idx & idx); } } return sum; } Here's an example for getting the actual frequency for index 12:
Image 1.7  read actual frequency at some index in BIT (image shows example for index 12) Let's compare algorithm for reading actual frequency at some index when we twice use function read and the algorithm written above. Note that for each odd number, the algorithm will work in const time O(1), without any iteration. For almost every even number idx, it will work in c * O(log idx), where c is strictly less than 1, compare to read(idx)  read(idx  1), which will work in c1 * O(log idx), where c1 is always greater than 1. Time complexity: c * O(log MaxVal), where c is less than 1. Scaling the entire tree by a constant factor void scale(int c){ for (int i = 1 ; i <= MaxVal ; i++) update((c  1) * readSingle(i) / c , i); } This can also be done more quickly. Factor is linear operation. Each tree frequency is a linear composition of some frequencies. If we scale each frequency for some factor, we also scaled tree frequency for the same factor. Instead of rewriting the procedure above, which has time complexity O(MaxVal * log MaxVal), we can achieve time complexity of O(MaxVal): void scale(int c){ for (int i = 1 ; i <= MaxVal ; i++) tree[i] = tree[i] / c; } Time complexity: O(MaxVal). Find index with given cumulative frequency // if in tree exists more than one index with a same // cumulative frequency, this procedure will return // some of them (we do not know which one) // bitMask  initialy, it is the greatest bit of MaxVal // bitMask store interval which should be searched int find(int cumFre){ int idx = 0; // this var is result of function while ((bitMask != 0) && (idx < MaxVal)){ // nobody likes overflow :) int tIdx = idx + bitMask; // we make midpoint of interval if (cumFre == tree[tIdx]) // if it is equal, we just return idx return tIdx; else if (cumFre > tree[tIdx]){ // if tree frequency "can fit" into cumFre, // then include it idx = tIdx; // update index cumFre = tree[tIdx]; // set frequency for next loop } bitMask >>= 1; // half current interval } if (cumFre != 0) // maybe given cumulative frequency doesn't exist return 1; else return idx; } // if in tree exists more than one index with a same // cumulative frequency, this procedure will return // the greatest one int findG(int cumFre){ int idx = 0; while ((bitMask != 0) && (idx < MaxVal)){ int tIdx = idx + bitMask; if (cumFre >= tree[tIdx]){ // if current cumulative frequency is equal to cumFre, // we are still looking for higher index (if exists) idx = tIdx; cumFre = tree[tIdx]; } bitMask >>= 1; } if (cumFre != 0) return 1; else return idx; } Example for cumulative frequency 21 and function find:
Time complexity: O(log MaxVal). 2D BIT
If m is the number of queries, max_x is maximum x coordinate, and max_y is maximum y coordinate, then the problem should be solved in O(m * log (max_x) * log (max_y)). In this case, each element of the tree will contain array  (tree[max_x][max_y]). Updating indexes of xcoordinate is the same as before. For example, suppose we are setting/removing dot (a , b). We will call update(a , b , 1)/update(a , b , 1), where update is: void update(int x , int y , int val){ while (x <= max_x){ updatey(x , y , val); // this function should update array tree[x] x += (x & x); } } The function updatey is the "same" as function update: void updatey(int x , int y , int val){ while (y <= max_y){ tree[x][y] += val; y += (y & y); } } It can be written in one function/procedure: void update(int x , int y , int val){ int y1; while (x <= max_x){ y1 = y; while (y1 <= max_y){ tree[x][y1] += val; y1 += (y1 & y1); } x += (x & x); } } Image 1.8  BIT is array of arrays, so this is twodimensional BIT (size 16 x 8). Blue fields are fields which we should update when we are updating index (5 , 3). The modification for other functions is very similar. Also, note that BIT can be used as an ndimensional data structure.
References


Home 
About TopCoder 
Press Room 
Contact Us 
Careers 
Privacy 
Terms
Competitions  Cockpit 
Copyright TopCoder, Inc. 2001 