Fenwick Tree or Binary Indexed Tree(BIT)

We are given an array a[], and we want to be able to perform two types of operations on it.
  1. Change the value stored at an index i. (This is called a point update operation)
  2. Find the sum of a prefix of length k. (This is called a range sum query)
Solving this question using brute force method would result in a time complexity of O(k) for finding the sum. 

Using segment tree the same can be done in O(logK) time.

How much better can BIT do to the time complexity? 

Ans: No Better.. Time complexity will be same as O(logK)

Then why use it?

Ans: Because binary indexed trees require less space and are very easy to implement during programming contests (the total code is not more than 8-10 lines). 


We know the fact that each integer can be represented as sum of powers of two. Similarly, for a given array of size N, we can maintain an array BIT[] such that, at any index we can store sum of some numbers of the given array. This can also be called a partial sum tree.





               {           a[x],                  if x is odd
BIT[x] =                    a[1] + ... + a[x],     if x is power of 2
               }


To generalize this every index i in the BIT[] array stores the cumulative sum from the index           i to i - (1<<r) + 1 (both inclusive), where r represents the last set bit in the index i

Sum of first 12 numbers in array a[] = BIT[12] + BIT[8] = (a[12] + … + a[9]) + (a[8] + … + a[1])




Notes:

Before going for Binary Indexed tree to perform operations over range, one must confirm that the operation or the function is:
  • Associative. i.e f(f(a, b), c) = f(a, f(b, c)) this is true even for seg-tree
  • Has an inverse. 

Operations(Templates):-


Update: (point)


void update(int x, int delta)       //add "delta" at index "x"
{
    for(; x <= n; x += x&-x)
          BIT[x] += delta;
}

x&(-x) gives the last set bit in a number x.

Update operation takes at most O(log(n)) time.


Suppose we call update(13, 2).  (A[13]+=2)

Here we see from the above figure that indices 13, 14, 16 cover index 13 and thus we need to add 2 to them also.

Initially x is 13, we update BIT[13]

    BIT[13] += 2;

Now isolate the last set bit of x = 13(1101) and add that to x , i.e. x += x&(-x)
Last bit is of x = 13(1101) is 1 which we add to x, then x = 13+1 = 14, we update BIT[14]

    BIT[14] += 2;

Now 14 is 1110, isolate last bit and add to 14, x becomes 14+2 = 16(10000), we update BIT[16]

    BIT[16] += 2;

In this way, when an update() operation is performed on index x we update all the indices of BIT[] which cover index x and maintain the BIT[].


Query:

int query(int x)      //returns the sum of first x elements in given array a[]
{
     int sum = 0;
     for(; x > 0; x -= x&-x)
         sum += BIT[x];
     return sum;
}

Talking about complexity, again we can see that the loop iterates at most the number of bits in x which will be at most n(the size of the given array). Thus the *query operation takes O(log(n)) time *.



Space Complexity: O(N) for declaring another array of size N
Time Complexity: O(logN) for each operation(update and query as well)



Having Doubts ?

Reference Links: 



Lets Jump to some questions :

Question 1: Link to Question

Query 0:- modify the element present at index i to x.
Query 1:- count the number of even numbers in range l to r inclusive.
Query 2:- count the number of odd numbers in range l to r inclusive.

   Input                                         Output
6                     2
1 2 3 4 5 6            2 
4                     4 
1 2 5
2 1 4
0 5 4
1 1 6
Solution:
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
int BIT[MAX],a[MAX];

void update(int idx,int val){
    for(int i=idx;i<MAX;i+=i&(-i))
        BIT[i]+=val;
}

int query(int val){
    int ret=0;
    while(val){
        ret+=BIT[val];
        val-=val&(-val);
    }
    return ret;
}

int main(){
    int n,i;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]%2==0)
        upd(i,1);
    }
    int q,l,r,ch;
    cin>>q;
    while(q--){
        cin>>ch>>l>>r;
        if(ch==0){
            if(r%2==1&&a[l]%2==0)
            upd(l,-1);
            if(r%2==0&&a[l]%2==1)
            upd(l,1);
            a[l]=r;
        }
        else if(ch==1){
            int cnt=query(r)-query(l-1);
            cout<<cnt<<endl;
        }
        else{
            int cnt=query(r)-query(l-1);
            cout<<(r-l+1)-cnt<<endl;
        }
    }
}
  Question 2: Another query question
  
  Given a sorted array A, you have to answer two types of queries

   1 X Subtract 1 from each element whose index is in the range[1,X]

   2 Y Check if Y exists in the array.
  
  Input                                                 Output

  7 yes
1 2 3 4 5 6 7 no
7
1 5
1 1
2 3
1 7
1 10
1 5
2 -5

 Explanation:

 Since initially the array given is sorted and the second query requires to search for an element in the array, so in order to apply binary search over the array, we need to maintain the sorted property of the array even after applying the 1st query (subtracting 1 from 1 to X). How do we do that?

Say for example we have we have initial BIT array value as all zero.

Now we can preserve the values using prefix sum for each node, and in order to do that we point update value at 1 by -1 and at X+1 by +1. How does this work?

                                                                                       
 Say we have a array  BIT  with values  : 0 0 0 0 0 0 0 initially

for each input in array we call update(idx,a[idx]) and update(idx+1,-a[idx])

Input: 1      call update(1,1) and update(2,-1)    BIT: 1 0 0 0 0 0 0
Input: 2      call update(2,2) and update(3,-2)    BIT:  1 2 -2 0 0 0 0
Input:3
.
.
.
Input: 7    call update(7,1) and update(8,-1)      BIT:  1 2 1 4 1 2 1

Now if we call our query function for each i from 1 to n we get the prefix sum.

And the prefix sum comes as 1 2 3 4 5 6 7 (calling query(i) for each i)

That is the beauty of this thing. The prefix sum stores the value that we inserted.

Now if there is a query say 1 5 ( subtract value from index 1 to 5 by 1)

Expected Array values: 0 1 2 3 4 6 7

call update(1,1) and update(6,-1) the BIT array becomes 

0  1 1 3 1 3 1

Now calling query(i) again i.e prefix sum we get the values as

0 1 2 3 4 6 7 (which is the expected array values)


Solution:


#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX 100009
ll BIT[MAX],a[MAX];

void update(ll idx,ll val){
    for(ll i=idx;i<MAX;i+=i&(-i))
        BIT[i]+=val;
}

ll query(ll val){
    ll ret=0;
    while(val){
        ret+=BIT[val];
        val-=val&(-val);
    }
    return ret;
}

void solve(ll lo,ll hi,ll x){
 bool ans = false;
 ll mid,tmp;
 while (lo<=hi)
 {
  mid = (lo+hi)/2;
  tmp = a[mid]+query(mid);
  if (tmp==x)
  {
   ans = true;
   break;
  }
  else if (tmp<x)
   lo = mid+1;
  else if (tmp>x)
   hi = mid-1;
 }
 if (!ans) 
  cout<<"no"<<endl;
 else 
  cout<<"yes"<<endl;
}

int main(){
    ll n,i;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    ll q,x,ch;
 bool ans;
    cin>>q;
    while(q--){
        cin>>ch>>x;
        if(ch==1){
            update(1,-1);
            update(x+1,1);
        }
        if(ch==2)
            solve(1,n,x);
    }
}


 Question 3: INVCNT (Inversion Count)

 Find number of pairs such that a[i]>a[j] and i < j.

 Input                                Output
 5
 9 1 0 5 4                            6

Explanation:

The idea is to iterate the array from n-1 to 0. When we are at i'th index, we check how many numbers less than arr[i] are present in BIT and add it to the result. To get the count of smaller elements, query() of BIT is used.

After that we add current element to to the BIT[] by doing an update operation that updates count of current element from 0 to 1, and therefore updates ancestors of current element in BIT.


Solution:


#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
int BIT[MAX],a[MAX];

#define ll int

void update(int idx,int val){
    for(int i=idx;i<MAX;i+=i&(-i))
        BIT[i]+=val;
}

int query(int val){
    int ret=0;
    while(val){
        ret+=BIT[val];
        val-=val&(-val);
    }
    return ret;
}

void convert(int n)
{
 int temp[n];
 for (int i=0; i<n; i++)
  temp[i] = a[i];
 sort(temp, temp+n);

 for (int i=0; i<n; i++)
  a[i] = lower_bound(temp, temp+n, a[i]) - temp + 1;
}

int main(){
    int n,i,cnt=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    convert(n);
    for (int i=n-1; i>=0; i--)
 {
  cnt += query(a[i]-1);
  update(a[i], 1);
 }

 cout<<cnt<<endl;
}



Practice Problems:
























Comments

Post a Comment

Popular posts from this blog

Lazy Propagation - Too lazy to update all at a time

Image
Sometimes problems will ask you to update an interval from  l to r , instead of a single element. One solution is to update all the elements one by one. Complexity of this approach will be  O(N)  per operation since where are  N  elements in the array and updating a single element will take  O(logN)  time. To avoid multiple call to update function, we can modify the update function to work on an interval. For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we need to update this node and all descendants of this node. With Lazy propagation, we update only node with value 27 and postpone updates to its children by storing this update information in separate nodes called lazy nodes or values. We create an array lazy[] which represents lazy node. Size of lazy[] is same as array that represents segment tree, which is tree[] in below code. The idea is to initialize
Read more

Combinatorial Game Theory

Image
Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints. These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find. First, we will look at the basic division of positions to winning and losing . Question:  Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner. Approach:  As we can see positions 1, 3 and 4 are winning positions since the
Read more

Bit Manipulation Problems

We may face many Interview Questions which can ask us to find the Sum of XOR of all pairs of the array OR  Sum of XOR of all subsets   Generally, the constraints for these questions are very high with the value of each array element to be as large as 10^18. So that is a catch to use Bit manipulation method to solve the questions. We will be discussing some of these questions in this post.   Question  1:  Sum of XOR of all possible subsets   Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all   the elements of the subsets.   Input                                                Output  3                                                       28  1 5 6   Explanation:  The most important clue for solving these questions is to find a pattern  with respect to the                property of XOR .  1 = 001 5 = 101 6 = 110 1 ^ 5 = 100 1 ^ 6 = 111 5 ^ 6 = 011 1^5^6 = 010 Total number of subs
Read more