ideone

useful pieces of codes

View on GitHub

Description

Fenwick Tree (also known as Binary Indexed Tree). This is usefull for efficiently storing the prefix sums of an array which have frequent updates.

Properties

Initialize the class with the max and min limits of the input indexes. By default it works over all positive int.
data type of max and min limits is int. This restricts the allowed range of index numbers to be over int only.
To change this behaviour we need to make changes in the implementation (which is good), otherwise we might end up with an overflow error in some scenario.

method set will add the value d at the index I given to the method.
method get will return the sum of all the value with index less than or equal to I.

Complexity

Time: O(log(N)) = O(1) for both get and set operations
Space: O(n * log(N)) overall space used in worst case

Naive method

set Time: O(log(n)) ~ O(log(N)) ~ O(1) insertion in an ordered map
get Time: O(n) iterate upto the last element in worst case
Space: O(n)

Other naive implementation is to store the prefix sums instead of the values itself, but that will only flip the time complexity for get and set operations, keeping the overall complexity same if both the operations are equally frequent.

Legend

n: number of unique indexes for which the updates may come
N: size of the range of the input numbers, i.e., max-min+1

Code

https://ideone.com/dIYSUb

to cater range updates as well, we can use two trees smartly as depicted here

https://ideone.com/PdaqdH

Usage

Code

#include <iostream>
#include <unordered_map>
#include <map>
#include <climits>
using namespace std;
template <class T>
class FenwickTree{
private:
    unordered_map<long long, T> v;
    long long ma;
    long long mi;
public:
    FenwickTree(int max = INT_MAX, int min = 1) : ma(max), mi(min-1L) {}
    void set(long long i, T d){
        if(i<=mi||i>ma) throw "bad_allocation";
        i -= mi;
        while(i<=ma-mi){
            v[i] += d;
            i += i&-i;
        }
    }
    T get(long long i){
        if(i<=mi)   return 0;
        if(i>ma)    i = ma;
        i -= mi;
        T x = NULL;
        while(i){
            x += v[i];
            i -= i&-i;
        }
        return x;
    }
};
class PrefixSum{
private:
    map<int, int> v;
public:
    void set(int i, int d){
    	v[i] += d;
    }
    int get(int i){
    	int x = 0;
    	for(auto p: v)
    		if(p.first>i)	break;
    		else	x += p.second;
    	return x;
    }
};
int main() {
	int n,q,p;
	cin>>n>>q>>p;
	p %= 101;	// p: should be a percentage
	FenwickTree<int> ft(n,1);
	PrefixSum ps;
	int i,d;
	while(q--){
		i = 1+rand()%n;
		d = rand()%100;
		if(d<p){
			if(ft.get(i)!=ps.get(i))
				cout<<"Mismatch at i = "<<i<<" q = "<<q<<endl;
		}
		else{
			d = rand()%100;
			ft.set(i,d);
			ps.set(i,d);
		}
	}
	if(ft.get(n)!=ps.get(n))
		cout<<"Final query mismatch"<<endl;
	else
		cout<<"Comparison finished"<<endl;
	return 0;
}

Ideone it!

#include <iostream>
#include <unordered_map>
#include <map>
#include <climits>
using namespace std;
template <class T>
class FenwickTree{
private:
    unordered_map<long long, T> v;
    long long ma;
    long long mi;
public:
    FenwickTree(int max = INT_MAX, int min = 1) : ma(max), mi(min-1L) {}
    void set(long long i, T d){
        if(i<=mi||i>ma) throw "bad_allocation";
        i -= mi;
        while(i<=ma-mi){
            v[i] += d;
            i += i&-i;
        }
    }
    T get(long long i){
        if(i<=mi)   return NULL;
        if(i>ma)    i = ma;
        i -= mi;
        T x = NULL;
        while(i){
            x += v[i];
            i -= i&-i;
        }
        return x;
    }
};
template <class T>
class FenwickTree2 {
private:
	int ma;
	int mi;
	FenwickTree<T> ft1;
	FenwickTree<T> ft2;
public:
	FenwickTree2(int max = INT_MAX, int min = 1) : ft1(max,min), ft2(max,min), ma(max), mi(min) {}
	void set(long long l, long long r, T d){
		if(l>r)	throw "bad_allocation";
		ft1.set(l,d);
		ft2.set(l,d*(l-1));
		if(r==ma)	return;
		ft1.set(r+1,-d);
		ft2.set(r+1,-d*r);
	}
	void set(long long i, T d){
		set(i,i,d);
	}
	T get(long long i){
        if(i>ma)    i = ma;
		return i*ft1.get(i) - ft2.get(i);
	}
};
class PrefixSum{
private:
    map<int, int> v;
public:
    void set(int i, int d){
    	v[i] += d;
    }
    int get(int i){
    	int x = 0;
    	for(auto p: v)
    		if(p.first>i)	break;
    		else	x += p.second;
    	return x;
    }
};
int main() {
	int n,q,p;
	cin>>n>>q>>p;
	p %= 101;	// p: should be a percentage
	int offset = -50;
	FenwickTree2<int> ft(n-1+offset,offset);
	PrefixSum ps;
	int i,d;
	while(q--){
		i = offset+rand()%n;
		d = rand()%100;
		if(d<p){
			if(ft.get(i)!=ps.get(i))
				cout<<"Mismatch at i = "<<i<<" q = "<<q<<endl;
		}
		else{
			d = rand()%100;
			ft.set(i,d);
			ps.set(i,d);
		}
	}
	if(ft.get(n-1+offset)!=ps.get(n))
		cout<<"Final query mismatch"<<endl;
	else
		cout<<"Comparison finished"<<endl;
	return 0;
}

Ideone it!

Usage