Fenwick Tree to Maintain A count of number of even numbers

Q: Design a Fenwick Tree to maintain a count of even numbers.


References to Learn about Fenwick Trees

• HackerEarth
• Wikipedia

Language: C++

Code

 

#include <iostream>
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
 
lli arr[100005];//stores actual numbers
int even[100005];//bit array with the tree
int n;
 void insert(lli x, int i){//to insert new numbers in tree
 arr[i]=x;
 if(x%2==0)
 while(i<=n){
  even[i]++;
  i+=(i&-i);//bit op magic
 }
 
}
 
 void update(lli x,int i){// to update a number at a given index
 if((arr[i]%2)==x%2) {arr[i]=x; return;}
 arr[i]=x;
 if(x%2==0){
  while(i<=n){
  even[i]++;
  i+=(i&-i); //bit map magic
 }
 }
 else{
  while(i<=n){
  even[i]--;
  i+=(i&-i);
 }
 }
}
 //returns the number of even numbers upto index i
 int query(int i){ 
 int ans=0;
 while(i>0){
  ans+=even[i];
  i-=(i&-i);// bit op magic
 }
 return ans; 
}

 

Bitop Magic 

The bitop Magic looks pretty magical and geeky. Turns out its pretty simple. You need to know these things:

1. How are numbers stored in computers?
2. Two's complement of number!
3. Bitwise and operation

  When the variable i is the number then -i is nothing but the complement.

So what exactly is i & -i. What will it do? I suggest you try working it out on your own, before you continue reading.


Hope you have worked it out. In case not here's what it does:

1. i is odd then i&-i will give 1
2. i is even but not multiple of 4 then you get 2
3. i is multiple of 4 but not 8 then you get 4
4. i is multiple of 8 but not 16 then you get 8
5. and so on.

Bitop magic is the reason due to which a Fenwick tree can obtain a log(n)  complexity for insert, update and search.