Fenwick (Binary Indexed) Trees

Fenwick প্রোগ্রামিং প্রবলেম (Programming Problem in Bengali)(Binary Indexed) Trees

Fenwick Tree 

Where's the tree in Fenwick tree? 

visualgo

kartikkukreja 

ডাটা স্ট্রাকচার: বাইনারি ইনডেক্সড ট্রি

Topcoder Algorithm 

Zobayer blog ( see also Felix halim comment) 

CF blog 

Youtube Video:

Algorithms live 

Bangla Tutorial 

Implementation 01:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

//Space Complexity: O(N) // Time Complexity: O(NlogN) #include<bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 10005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int BIT[MAX], n; int a[MAX] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; void update(int x, int val) { for(; x <= n; x += x & (-x)) BIT[x] += val; } int query(int x) { int sum = 0; for(; x > 0; x -= x & (-x)) sum += BIT[x]; return sum; } int main() { //FASTIO ///* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ scanf("%d", &n); int i; for(i = 1; i <= n; i++) { scanf("%d", &a[i]); update(i, a[i]); } printf("sum of first 10 elements is %d\n", (query(10)) ); printf("sum of all elements in range [2, 7] is %d\n", (query(7) - query(2 - 1)) ); //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

2D BIT:

	///O((NM+Q).log(NM))
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 5
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	const int N = 4;
	struct Query
	{
	int x1, y1; // bottom left
	int x2, y2; // top right
	};
	void update(int Bit[][N + 1], int x, int y, int val)
	{
	for (; x <= N; x += (x & -x)) {
	for (; y <= N; y += (y & -y))
	Bit[x][y] += val;
	}
	return;
	}
	// A function to get sum from (0, 0) to (x, y)
	int getSum(int Bit[][N + 1], int x, int y)
	{
	int sum = 0;
	for (; x > 0; x -= (x & -x)) {
	for (; y > 0; y -= (y & -y)) {
	sum += Bit[x][y];
	}
	}
	return sum;
	}
	void constructAux(int mat[][N], int aux[][N + 1])
	{
	for (int i = 0; i <= N; i++) {
	for (int j = 0; j <= N; j++) {
	aux[i][j] = 0;
	}
	}
	for (int j = 1; j <= N; j++) {
	for (int i = 1; i <= N; i++) {
	aux[i][j] = mat[N - j][i - 1];
	}
	}
	return;
	}
	void construct2DBIT(int mat[][N], int Bit[][N + 1])
	{
	int aux[N + 1][N + 1];
	constructAux(mat, aux);
	for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= N; j++)
	Bit[i][j] = 0;
	}
	for (int j = 1; j <= N; j++) {
	for (int i = 1; i <= N; i++) {
	int a = getSum(Bit, i, j);
	int b = getSum(Bit, i, j - 1);
	int c = getSum(Bit, i - 1, j - 1);
	int d = getSum(Bit, i - 1, j);
	update(Bit, i, j, aux[i][j] - (a - b - d + c));
	}
	}
	return;
	}
	void answerQueries(Query q[], int m, int Bit[][N + 1])
	{
	for (int i = 0; i < m; i++) {
	int x1 = q[i].x1 + 1;
	int y1 = q[i].y1 + 1;
	int x2 = q[i].x2 + 1;
	int y2 = q[i].y2 + 1;
	int ans = getSum(Bit, x2, y2) - getSum(Bit, x2, y1 - 1) - getSum(Bit, x1 - 1, y2) + getSum(Bit, x1 - 1, y1 - 1);
	printf ("Query(%d, %d, %d, %d) = %d\n",
	q[i].x1, q[i].y1, q[i].x2, q[i].y2, ans);
	}
	return;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int mat[N][N] = {
	{1, 2, 3, 4},//3
	{5, 3, 8, 1},//2
	{4, 6, 7, 5},//1
	{2, 4, 8, 9}//0
	}; //0 1 2 3
	int Bit[N + 1][N + 1];
	construct2DBIT(mat, Bit);
	Query q[] = {{1, 1, 3, 2}, {2, 3, 3, 3}, {1, 1, 1, 1}};
	int m = sizeof(q) / sizeof(q[0]);
	answerQueries(q, m, Bit);
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw 2DBit.cpp hosted with ❤ by GitHub

Problem:

Binary Indexed Trees with some Solved Example.

Spoj:

TRIPINV - Mega Inversions 

INVCNT - Inversion Count 

YODANESS - Yodaness Level 

INCSEQ - Increasing Subsequences 

HORRIBLE - Horrible Queries 

CTRICK - Card Trick 

MATSUM - Matrix Summation 

NICEDAY - The day of the competitors 

DQUERY - D-query 

MCHAOS - Chaos Strings 

Codeforces:

C. Little Girl and Maximum Sum 

D. Pashmak and Parmida's problem 

LightOj:

1112 - Curious Robin Hood  Solution

 

 

Share: