How to use Binary Indexed tree to count the number of elements that is smaller than the value at index?

Question

The problem is to count the number of of values less than the value after index. Here is the code, but I can't understand how binary indexed tree has been used to do this?

#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
#define MOD 1000000007
#define MAXN 10
using namespace std;
typedef pair<int, int> ii;
int BIT[MAXN+1];
int a[MAXN+1];
vector< ii > temp;
int countSmallerRight[MAXN+1];
int read(int idx) {
    int sum = 0;
    while (idx > 0) {
    sum += BIT[idx];
    idx -= (idx & -idx);
    }
    return sum;
}
void update(int idx, int val) {
    while (idx <= MAXN) {
    BIT[idx] += val;
    idx += (idx & -idx);
    }
}
int main(int argc, const char * argv[])
{
int N;

scanf("%d", &N);

 for (int i = 1; i <= N; i++) {
    scanf("%d", &a[i]);
    temp.push_back(ii(a[i], i));
    }

sort(temp.begin(), temp.end());
countSmallerRight[temp[0].second] = 0;
update(1, 1);
update(temp[0].second, -1);

for (int i = 1; i < N; i++) {
    countSmallerRight[temp[i].second] = read(temp[i].second);
    update(1, 1);
    update(temp[i].second, -1);
}
for (int i = 1; i <= N; i++) {
    printf("%d,", countSmallerRight[i]);
}


putchar('\n');


return 0;


}

It would be helpful if someone could explain the working principal of the code.

Answer 1

to understand BIT this is one of the best links .
TC gives the full explaination of functions you used , but rest part is logic on how to use it .
For basic understanding :

ques: there are n heaps and in each heap initially there are 1 stones then we add stones from u to v…find how much stone are there in given heap.

the solution , with answer at each iteration is http://pastebin.com/9QJ589VR. After you understand it , try to implement your question .

Answer 2

A better proof and motivation behind Binary Index trees can be found here. https://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a

Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements. You could start off by writing out seven buckets into which the numbers will be distributed

Change the representation from being an array of buckets to being a binary tree of nodes.

If you treat 0 to mean "left" and 1 to mean "right," the remaining bits on each number spell out exactly how to start at the root and then walk down to that number.

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links. For example, during a lookup, we just care about the right links we follow. During an update, we just care about the left links we follow. This binary indexed tree does all of this super efficiently by just using the bits in the index.

If you don't care about the proof:

I googled BIT for dummies and found this https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

Property of a perfectly binary tree: Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.

Why isolate the last bit?

When we isolate the last bit, the index x only goes to indexes ((+/-)x&(-x)) whose update is neccesary or whose value is required during a lookup.

while query we go down the array and while update we go up the array.

For example query(6) is going to add sum at BIT[6] but also add sum at BIT[4] and BIT[0] because 6(110) - 2 = 4(100) - 4 = 0. 6(110)'s last bit is 2(10). Hence we do 6-2. 4(100)'s last bit is 4(100). Hence we do 4-4. we stop when x==0.

Use the same logic for update just add, dont subtract. One dry run should be enough to convince you that its really magical! Also BIT is 1-based.

    public static void update(int x, int val, int size){
        //int k =x;
        x++;
        for (; x<size; x+= x&(-x))
            BIT[x]+=val;
    }
    public static int query(int x){
        //int k =x;
        int toreturn =0;
        for (; x >0; x-= x&(-x)) 
            toreturn+=BIT[x];
        return toreturn;
    }
    public static List<Integer> countSmaller(int[] nums) {
        // will only  work for positive numbers less that 7. 
        // I arbitrarily set the size to 7, my code my choice
        int size = 7;
        BIT = new int[size];
        List<Integer> result = new ArrayList<Integer>();

        for (int i =nums.length-1; i >=0; i--) {
            int smaller_count = query(nums[i]);
            result.add(smaller_count);
            update(nums[i], 1, size);
        }
        Collections.reverse(result);
        return result;
    }