বাইনারি ইন্ডেক্সড ট্রি অথবা ফেনউইক ট্রি ( Binary Indexed Tree or Fenwick Tree )

কোন অ্যারের সংখ্যাগুলোর যোগফল বের করতে, কোন ইনডেক্স আপডেট করতে আমরা বাইনারি ইন্ডেক্সড ট্রি ব্যবহার করি। এসব কাজ আমরা সেগমেন্ট ট্রি দিয়েও করতে পারি, কিন্তু Binary Indexed Tree (BIT) দিয়ে কোড করা অনেক সহজ এবং খুব দ্রুত কোড করে ফেলা যায়। আসলে এই BIT ঠিক কি কাজে লাগে? 

• কোন অ্যারের 0 থেকে N পর্যন্ত যোগফল, মিনিমাম, ম্যাক্সিমাম ইত্যাদি বের করা
• কোন ইন্ডেক্স আপডেট করা

লক্ষ্য রাখতে হবে যে, BIT দিয়ে আমরা 0 থেকে যেকোন রেঞ্জ এর কিছু অপারেশন ক্যাল্কুলেট করবো। এখানে আমরা 1 বেস ইনডেক্স নিয়ে আলোচনা করবো।
আমরা নরমালি যোগফল লুপ চালায়ে বের করতেই পারি, কিন্তু BIT আমাদের এই কাজকে O(logN) এ করে দেয়।

BIT শুরু করার আগে একটু bit নিয়ে কাজ করা যাক। 

আমরা যেকোন একটি নম্বর এর সর্বশেষ সেট(1) বিটকে সরানোর চেষ্টা করি, কেন করছি, তা পরে বলি।
ধরি, একটি নম্বর = 14. একে বাইনারি তে নিলে হবে = 1110 (যেহেতু বিট এর হিসাব সব বাইনারিতে হয়, আমরা বাইনারি নিয়ে বেশি মাথা ঘামাবো)

এখন এই 1110 এর সর্বশেষ সেট বিট হচ্ছে 1 নং পজিশন এ।

এখন আমাদের কাজ হল এই 1 পজিশন এর বিট 1 কে সরানো। আমরা এটি করতে পারি এভাবেঃ x & (-x)

এখানে x = 14; অর্থাৎ আমরা একটি অ্যান্ড অপারেশন এর মাধ্যমে এটি করতে পারি।

x = 14 = 1110

x = -14 = 0010

x & (-x) = 1110 & 0010 = 10 (আমরা এভাবে সর্বশেষ সেট বিট কে আলাদা করে ফেললাম)

এখন কথা হচ্ছে, কেন আমরা এভাবে আলাদা করে ফেললাম? একটু পরেই আমরা বুঝতে পারবো। এখন আমরা সরাসরি BIT এর মাঝে চলে যাবো।

বাইনারি ইন্ডেক্সড ট্রি ( Binary Indexed Tree )

আমরা জানি, যেকোন সংখ্যা কে ২ এর পাওয়ারের যোগফল আকারে লিখা যায়। আমরা ধরে নেই আমাদের একটি অ্যারে আছে যার নাম BIT অ্যারে। এখানে আমরা যেকোন ইনডেক্স এ অ্যারের কিছু সংখ্যার যোগফল রাখবো। অর্থাৎ এটি আমাদের একটি পারশিয়াল সাম ট্রি হিসাবে কাজ করবে।

ধরি আমাদের একটি অ্যারে আছে A[ ]. এবং আমাদের partial sum সেভ করে রাখার জন্য আছে BIT[ ] অ্যারে। ধরি আমাদের A[ ] অ্যারের ইনডেক্স ১ বেসড। এখনঃ
A [ ] = { 1, 2, 3, 4, 5, 6 }

এবং আমাদের BIT অ্যারে হবে এরকমঃ

BIT [ 1 ] = A [ 1 ] = 1

BIT [ 2 ] = A [ 1 ] + A [ 2 ] = 1 + 2 = 3

BIT [ 3 ] = A [ 3 ] = 3

BIT [ 4 ] = A [ 1 ] + A [ 2 ] + A [ 3 ] + A [ 4 ] = 10

BIT [ 5 ] = A  [5 ] = 5

BIT [ 6 ] = A [ 5 ] + A [ 6 ] = 11

এটি একটি বাইনারি ইন্ডেক্সড ট্রি এবং BIT [ index ] এর মাঝে আমাদের A অ্যারের partial sum সেভ করা আছে।

অর্থাৎ,

BIT [ n ] =   A [ n ] ; if n is odd

                     A [ 1 ] + A [ 2 ] + ... + A [ n ]; if n is power of 2

আমরা প্রতিবার আমাদের BIT অ্যারেকে আপডেট করার মাধ্যমে ভ্যলুগুলি জেনারেট করবো। প্রতিবার আমরা A অ্যারের প্রতি ইনডেক্স এর জন্য আমাদের update(int index,int value) call করবো।
এখন প্রশ্ন আসতে পারে, যদি n এর মান বিজোড় কিংবা 2 এর পাওয়ার না হয়, তাহলে আমরা কি করবো? আমরা জানি যেকোন নম্বরকে 2 এর পাওয়ার হিসেবে লিখা যায়। আমাদের আপডেট ফাংশন 2 এর পাওয়ার না পেলে, তার ঠিক পরের 2 এর পাওয়ার পর্যন্ত ভ্যালুকে আপডেট করতে থাকবে। হাতে কলমে সিমুলেশন চালায়ে ব্যাপারটি দেখতে পারেন আপনারা।

	void update(int index,int value)
	{
	while(index <= n) // n is the size of A
	{
	BIT[index] += value;
	index += index & (-index);
	}
	}

view raw BIT_update.cpp hosted with ❤ by GitHub

ধরি আমরা update(5,2) call করলাম। এরমানে হচ্ছে, আমরা 5 ইনডেক্স কে 2 দিয়ে আপডেট করবো।
এখন, 5 = 101, BIT [ 5 ] += 2
আমাদের BIT [ 6 ] এও আপডেট করতে হবে, কাজেই আমরা যখন index & (-index) ব্যবহার করবো,
101 & 011 = 1; যা কিনা দশমিক এ 1। কাজেই আমরা 1 বারিয়ে দিব আমাদের কারেন্ট ইনডেক্স এর মান, এবং নতুন ইনডেক্স পাবো 6, কাজেই BIT [ 6 ] += 2 করে দিবো। এরপরে আমরা আবার একই কাজ করবো,
110 & 010 = 10; দশমিক এ ২, কাজেই নতুন ইনডেক্স = 6+2 = 8; কিন্তু 8 > 6, কারন আমরা A আ্যরের সাইজ নিয়েছি 6. এভাবে আমাদের আপডেট ফাংশন কাজ করে।

এখন কুয়েরি অপারেশন দেখা যাক।

	void query_sum(int index)
	{
	int sum = 0;
	while(index > 0)
	{
	sum += bit[index];
	index -= index & (-index);
	}
	return sum;
	}

view raw BIT_query_sum.cpp hosted with ❤ by GitHub

এখানে 1 থেকে index পর্যন্ত সংখ্যার যোগফল রিটার্ন করবে এই কুয়েরি ফাংশন। যেখা যাক কিভাবে কাজ করে,
আমরা 1 to 4 যোগফল চাই, তাহলে query_sum( 4 ) call করবো।
sum = 0
sum += BIT [4] = 0 + 10 = 10
4 = 100
so, 100 & 100 = 100 = 4 (decimal)
so index = index - 4 = 4 - 4 = 0 ; finally return sum;

আপডেট এবং কুয়েরি ২ ক্ষেত্রেই আমরা প্রতিটি ইনডেক্স এর বিট নিয়ে কাজ করছি, কাজেই উভয়খেত্রে আমাদের কমপ্লেক্সিটি O(logN)

কোডঃ

	#include <bits/stdc++.h>
	using namespace std;
	int BIT[1000], A[1000], n;
	void update(int index,int value)
	{
	while(index <= n)
	{
	BIT[index] += value;
	index = index & (-index);
	}
	}
	void query_sum(int index)
	{
	int sum = 0;
	while(index > 0)
	{
	sum += bit[index];
	index -= index & (-index);
	}
	return sum;
	}
	int main()
	{
	scanf(“%d”, &n);
	int i;
	for(i = 1; i <= n; i++)
	{
	scanf(“%d”, &a[i]);
	update(i, a[i]);
	}
	printf(“sum of first 6 elements is %d\n”, query_sum(6));
	printf(“sum of all elements in range [2, 6] is %d\n”, query(6) – query(2-1));
	return 0;
	}

view raw BIT_full.cpp hosted with ❤ by GitHub

এতক্ষন আমরা দেখলাম 1-D অ্যারের মাঝে যোগফল বের করা। আমাদের যদি 2-D অ্যারের মাঝে এরকম কোন কিছু করতে বলা হয়? তাহলে আমরা কিভাবে আপডেট এবং কুয়েরি চালাবো? ব্যাপারটি খুবি সোজা, যেভাবে আমরা 1-D এর জন্য করেছি, একই কাজ আমরা 2-D এর জন্যেও করবো ২ বার করে। বেশি কিছু না বলে কোড দেখা যাকঃ

	int a[1002][1002];
	int bit[1002][1002];
	int sum(int x,int y) // returns sum from (0,0) to (x,y) 2-D grid or rectangle
	{
	int sum = 0;
	for(int i = x; i >= 0; i = ( i & (i+1))-1)
	for(int j = y; j >= 0; j = ( j & (j+1))-1)
	sum += bit[i][j];
	return sum;
	}
	void update(int x,int y,int val) // update from (x,y) to max size of the grid
	{
	for (int i = x; i <= 1000; i = i | (i+1))
	for (int j = y; j <= 1000 ; j = j | (j+1))
	bit[i][j] += val;
	}

view raw BIT_full_2D.cpp hosted with ❤ by GitHub

এখানে i&(i+1)-1 এবং i|(i+1) দেখে ভয় পাবার কিছু নেই। আমরা এতক্ষন যা করেছি বিট দিয়ে, এখানেও তাই করা হয়েছে। একটু নিজে ঘাটাঘাটি করে দেখার অনুরোধ রইল।

প্র্যাকটিস প্রব্লেম ( Practice Problems )

• Uva: Potentiometers
• LightOJ: Curious Robin Hood
• LightOJ: Points in Rectangle
• Spoj: MATSUM
• Spoj: SUMSUM
• Spoj: INVCNT
• Hacker Earth: Counting in Byteland
• Hacker Earth: Akash and GCD1
• Codeforces: Little Artem and Time Machine
• Codeforces: Hanoi Factory
• Codeforces: Goodbye Souvenir
• Codeforces: Subsequences