BIT(Binary Indexed Tree /Fenwick Tree )

general
, ,
1

Hey just studied BIT from http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees but couldnot understand how to know to calculate tree[idx],it must be question dependent ?? So how to know what value to keep in that like was solving http://www.spoj.com/problems/MSE06H/ but could not get what value to store at the tree[idx] plzzz help guys…

1 Like
2

The problem is same as the problem LPAIR from FEB 2014 Cookoff. The only difference is that in problem MSE06H the pairs can repeat. You should try to handle that case yourself. The idea is that if we form an array consisting of second coordinate of each pair which(the array) is sorted first on the basis of first coordinate and then on the basis of second coordinate of that pair, then ans will be the number of inversions in the array. So, we form a BIT on this array such that a position tree[idx] is 1 if one or more pair with second coordinate equal to idx has occured or 0 if no such pair has occured. The operations on this BIT will be

  1. update(idx,1)- point update at index idx.
  2. read(idx) - Sum of tree[1]-tree[idx-1] which means no of inversions.
2 Likes