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 f…

Binary Indexed Tree.cpp

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)

Read cumulative frequency
If we want to read cumulative frequency for some integer idx, we add to sum tree[idx], substract last bit of idx from itself (also we can write - remove the last digit; change the last digit to zero) and repeat this while idx is greater than zero. We can use next function (written in C++)

int read(int idx){
	int sum = 0;
	while (idx > 0){
		sum += tree[idx];
		idx -= (idx & -idx);
	}
	return sum;
}