WAP to add a Marble to Box i & sum all the Marbles from Box k to box l .You Have Given The Number of Boxes.

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

we have to write an efficient algorithm & then code so that if do m queries in 2nd operation we can efficiently find out the sum of marbles from box i to box j.

This Question is Exactly Asked in Google Interview.

Solution

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). (BIT)Binary Indexed Trees are easy to code and have worst time complexity O(m log n).

(BIT)Fenwick tree supports the following basic operations each of which take O(log n) time:
Change the frequency at some position and update the tree
Read the cumulative frequency for a given key
Read the actual (not cumulative) frequency at a certain position
Find the index with a given cumulative frequency, if all individual frequencies are positive, or all indices with a given cumulative frequency, if all individual frequencies are non-negative
It also supports scaling all frequencies in the entire tree by a constant factor in O(n) time.


Algorithm

The two major functions are

update (idx,val) : increases the frequency of index idx with the value val
read (idx) : reads the cumulative frequency of index idx
Note : tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx where r is rightmost position of 1 in the binary notation of idx, f is frequency of index, c is cumulative frequency of index, tree is value stored in tree data structure.

Notataion

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.



Index
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

f
1 0 2 1 1 3 0 4 2 5 2 2 3 1 0 2

c
1 1 3 4 5 8 8 12 14 19 21 23 26 27 27 29

tree
1 1 2 4 1 4 0 12 2 7 2 11 3 4 0 29

Table 1.1



Index
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

tree
1 1..2 3 1..4 5 5..6 7 1..8 9 9..10 11 9..12 13 13..14 15 1..16

Table 1.2 – table of responsibility

#include
using namespace std;

template
class BIT
{
T *tree;
int maxVal;
public:
BIT(int N)
{
tree = new T[N+1];
memset(tree,0,sizeof(T)*(N+1));
maxVal = N;
}
void update(int idx, T val)
{
while (idx <= maxVal) { tree[idx] += val; idx += (idx & -idx); } } //Returns the cumulative frequency of index idx T read(int idx) { T sum=0; while (idx>0)
{
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
};

int main()
{
int a[100],cur=1,mul=2,add=19,MAX=65536,x,i;
//Initialize the size by the
//maximum value the tree can have
BIT B(MAX);
for (i=0;i<50 data-blogger-escaped-a="" data-blogger-escaped-add="" data-blogger-escaped-b.update="" data-blogger-escaped-cin="" data-blogger-escaped-cur="((cur" data-blogger-escaped-i="" data-blogger-escaped-max="" data-blogger-escaped-mul="" data-blogger-escaped-while="">>x)
{
cout< }

}

Time Complexity O(logn) fro m queries it will be O(mlogn)
Space Complexity O(1)
Source : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees