Segment tree/ BIT part - 1

সেগমেন্ট ট্রি এবং বাইনারি ইনডেক্স ট্রি কি এইটা নিয়ে লিখার আমার কোন ইচ্ছা নাই । এইটা নিয়া অনেক ভাল ব্লগ লিখা হইছে । কারো এইগুলা কি কোন আইডিয়া না থাকলে নিচের লিঙ্কগুলো থেকে শিখতে পারবে ।

•  সেগমেন্ট ট্রি - ১ 
•  সেগমেন্ট ট্রি - ২ 
•  বাইনারি ইনডেক্সড ট্রি 

এইখানে কিছু ভাল প্রবলেম কিভাবে আমরা উপরের দুইটা প্রসেস এর মাধ্যমে করতে পারি তা লিখার ইচ্ছা আছে । অনেক ভাল ভাল প্রবলেম আছে এই দুইটা টপিক এর । কয়েকটা সিরিজ লিখার ইচ্ছা আছে ( যদি কোনভাবে লিখার মোটিভেশন পাওয়া যায় :p ) ।

Calculate The Cost

আমাদের এইখানে বিভিন্ন গাছে পজিশন দেওয়া হবে তাদের ভ্যালু সহ তারপর আমাদের কিছু কুয়েরি করতে হবে যে ইনফরমেশন দেওয়া আছে তাদের উপর । আমাদের এই সব কুয়েরি তে  বলতে হবে যে এরিয়া ( x1 , y1 to x2 ,y2 ) এর মধ্যে কত ভ্যালু এর ট্রি আছে । এইখানে একটা জিনিস লক্ষ্য করার ব্যাপার হইল যদি আমাদের ইন্ডেক্স এর ( X , Y <= 10^3 ) এর মত হইত তাহলে আমরা খুব সহজে 2D Bit এর মাধ্যমে রেজাল্ট পেয়ে যাইতাম কিন্ত্ এইখানে দেওয়া আছে ( X , Y <= 10^7 ) । লিমিট অনেক বেশি বড় হওয়ায় আমরা কোন ভাবেই এত বড় সাইজের Array declear করতে পারি না । আমাদের এই প্রবলেমটাকে তাই কোন ভাবে 2D থেকে 1D তে নিয়ে এসে সল্ভ করতে হবে ।

আমি ধরে নিচ্ছি 2D solution কিভাবে হয় তা সবার জানা আছে । যদি না থাকে তাহলে index ( x1 , y1 ) to index ( x2 , y2 ) এর  মধ্যের ভ্যালু গুলার সাম হইল

Ans  =   BIT[x2][y2] - BIT[x1-1][y2] - BIT[x2][y1-1] + BIT[x1-1][y1-1] ;

এইটা কিভাবে আন্সার দিচ্ছে এইটা খাতায় একটা 2D grid একে , ইনডেক্স এর ভ্যালু বসিয়ে দেখলে বুঝে ফেলার কথা ।

এখন আমরা অফলাইন সল্যুশন কিভাবে হতে পারে তা দেখব ।

1. উপরের ফর্মুলাটা যদি লক্ষ্য করি তাহলে একটা জিনিস দেখি x1 row তে ( +Bit[x1-1][y1-1] - BIT[x1-1][y2] ) হচ্ছে । আবার x2 row ( + BIT[x2][y2] - BIT[x2][y1-1] ) হচ্ছে । 
2. অর্থাৎ আমরা যদি আমাদের দেওয়া ভ্যালু গুলাকে ( অবশ্যই কুয়েরি সহ ) row এর ব্যাসিস এ সর্ট করি তাহলে আমি column value ( y ইনডেক্স এর মান এর পজিশন ) তে 1D BIT চালাইয়া মান পেয়ে যেতে পারি । 
3. এইখানে একটা গুরুত্বপূর্ণ ব্যাপার হচ্ছে tree_point এর priority , opening point এর priority , closing_point এর priority যখন কিছু ভ্যালু সমান হয়ে যাবে । স্বাভাবিক ভাবেই পয়েক্ট এর  priority সব থেকে বেশি হবে । 

কোড ::

	const int MX = 1e7 + 10 ;
	const int XX = 50000 + 10 ;
	const int open = 1 ;
	const int point = 2 ;
	const int close = 3 ;
	struct abc
	{
	int x , y , val , priority , lim ;
	};
	abc inp[MX];
	Long tree[MX];
	Long ans[XX];
	bool cmp( abc A , abc B )
	{
	if( A.x == B.x )
	{
	return A.priority < B.priority ;
	}
	return A.x < B.x ;
	}
	void add( int x , int v )
	{
	while( x < MX )
	{
	tree[x] += v ;
	x += ( x & -x );
	}
	}
	Long sum( int x )
	{
	Long ans = 0 ;
	while( x )
	{
	ans += tree[x];
	x -= ( x & -x );
	}
	return ans ;
	}
	void solve()
	{
	// I will always use scanf and printf
	// May be i won't be a good programmer but i will be a good human being
	int cs , t ;
	scanf("%d",&t);
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	int n ;
	scanf("%d",&n);
	rep( i , n )
	{
	scanf("%d %d %d",&inp[i].x,&inp[i].y,&inp[i].val);
	inp[i].x++;
	inp[i].y++;
	inp[i].priority = point ;
	}
	int idx = n ;
	int r = II ;
	rep( i , r )
	{
	scanf("%d %d",&inp[i].x,&inp[i].y);
	inp[idx].x++;
	inp[idx].y++;
	inp[idx].priority = open ;
	inp[idx].val = i ;
	idx++;
	scanf("%d %d",&inp[i].x,&inp[i].y);
	inp[idx].x++;
	inp[idx].y++;
	inp[idx].priority = close ;
	inp[idx].val = i ;
	inp[idx-1].lim = inp[idx].y ;
	inp[idx].lim = inp[idx-1].y ;
	idx++;
	}
	sort ( inp , inp + idx , cmp );
	ms( tree , 0 );
	ms( ans , 0 );
	rep( i , idx )
	{
	if(inp[i].priority == point ) add( inp[i].y , inp[i].val );
	else if( inp[i].priority == open ) ans[inp[i].val] -= ( sum( inp[i].lim ) - sum( inp[i].y - 1 ) );
	else ans[inp[i].val] += ( sum(inp[i].y ) - sum( inp[i].lim - 1 ) );
	}
	rep( i , r ) printf("%lld\n",ans[i]);
	}
	}

view raw segone.cpp hosted with ❤ by GitHub

রান  টাইম হচ্ছে O( lim * log ( n + q ) )

New Land :::

সহজ কথায় আমাদের এই প্রবলেম এ বলছে আমরা হাইস্ট কত এরিয়ার একটা rectangle পাইতে পারি যেখানে কোন ১ নাই । এইখানে লিমিট অনেক বেশি row <= 2000 & column <= 2000 .যদি কম হইত ১০০ এর মত তাহলে আমরা Maximum SUM 2D এর মত করে সল্যুশন করে ফেলতে পারতাম । যেইটা এখন সম্ভব না । এই ধরনের প্রবলেম গুলার জন একটা অফ লাইন ট্যাকনিক আছে Stack use করে করা হয় । Histogram technique । যেটা আমরা এই প্রবলেমটা সমাধান করার জন্য ব্যাবহার করব । আগেই ক্ষমা চাইয়া নেই এই ধরনের কিছু বুঝানো জন্য ভাল ছবি দেওয়া দরকার , যেইটা রেডি করা একটু কস্টকর আমি নিজে অনেক অলস হওয়ায় এইটা করছি না । আমি যা লিখার চেস্টা করছি সব কিছুই পড়ার সাথে সাথে খাতায় ছবি এঁকে করলে ক্লিয়ার হবে ।

আমরা প্রবলেমটাকে কয়েকটা ভাগ এ সল্ভ করি ।

1.  commutative sum ( column wise ) । মানে আমরা যখন ১ পাব তখন ০ দিব যদি ০ পাই তাহলে ১ এড করে আগের row এর ভ্যালুর সাথে এড করে দিব । 
2. প্রতিটা পজিশন এর জন্য ডানে এবং বামে আমার কাছে এখন যে সাইজের Histogram আছে এর থেকে বড় বা সমান কতটা width এর বড় বিলিং করা যায় ( কথাগুলা না বুঝলে ভয় পাওয়ার কিছু নাই কোড দেখলেই বুঝা যাবে ) । 

কোড

	const int MX = 2005 ;
	int height[MX][MX] ;
	char str[MX][MX];
	int n , m , lft[MX] ;
	void solve()
	{
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II , m = II ; // ইনপুট নেওয়া হচ্ছে
	rep(i,n) scanf("%s",str[i]);
	rep(j,m) if( str[0][j] == '1' ) height[0][j] = 0 ; // প্রাথমিক ভাবে ফাস্ট রো এর জন্য করছি
	else height[0][j] = 1 ;
	For(i , n-1 ) rep( j , m ) if( str[i][j] == '1' ) height[i][j] = 0 ;
	else height[i][j] = height[i-1][j] + 1 ; // আমরা এর সাথে আগের রো এর সেভ করা ভ্যালু এড করে commutative sum current
	// position এর জন্য পাচ্ছি
	Long ans = 0 ;
	stack < int > st ;
	int j , r;
	rep(i,n) // 0 to n - 1
	{
	while( !st.empty() ) st.pop();
	rep(j,m) // o to m - 1
	{
	while( !st.empty() && height[i][st.top()] >= height[i][j] ) st.pop(); // maximum কত লেফট এ যাইতে পারি
	if( st.empty() ) lft[j] = 0 ; // একদম শুরুতেই চলে এসেছি
	else lft[j] = st.top() + 1 ; // আমাদের লেফট পজিশন
	st.push(j);
	}
	while( !st.empty() ) st.pop(); // এইটা করা অনেক ইম্পরট্যান্ট
	for ( j = m - 1 ; j >= 0 ; j-- )
	{
	while( !st.empty() && height[i][st.top()] >= height[i][j] ) st.pop(); // ম্যাক্সিমাম কত রাইটে যেতে পারি
	if( st.empty() ) r = m - 1 ; // একদমই শেষ এ চলে এসেছি
	else r = st.top() - 1 ; // আমার j পজিশন এর রাইট পজিশন
	if( (Long) ( r - lft[j] + 1 ) * height[i][j] > ans )
	ans =(Long) ( r - lft[j] + 1 ) * height[i][j]; // আন্সার আপডেট করছি
	st.push(j);
	}
	}
	printf("Case %d: %lld\n",cs,ans);
	}
	}

view raw segment2.cpp hosted with ❤ by GitHub

প্রুভ করি এইভাবে কেন কাজ করবে ।

1. আমরা যেহেতু column wise commutative sum রাখছি । তাহলে আমাদের প্রতিটা পজিশন এর জন্য ম্যাক্সিমাম হাইটের এবং Width এর বিলিং কত সাইজের পসিবল পাচ্ছি যাই আমাদের Ans এর সাথে চেক হচ্ছে । 
2. একটু ডিবাগ করলেই দেখব যে 0 height এর জন্য always left = 0 , right = m - 1 হইলেই যেহেতু হাইট দিয়ে গুণ হচ্ছে ঐ পজিশন এর জন্য আমার ০ এই পাওয়া যাচ্ছে ।

এইখানে run time O( n * m ) যেখানে আমরা যদি maximum sum 2D তে করতাম আমাদের লাগত O( n * m ^ 2 ) . 

একদমই একই রকমের একটা প্রবলেম হচ্ছে CTGAME ।

POSTERS :::

এই প্রবলেম এ আমাদের 1D কোন প্যানেল এ ইলেকশন পোস্টারের start position আর end position দেওয়া থাকবে । সিরিয়ালি যদি আমরা পোষ্টারগুলো লাগাই তাহলে শেষ পর্যন্ত কয়টি পোস্টার ভিজিবল থাকবে । এই প্রবলেমটা line sweep technique use করেও সল্ভ করা যায় । তবে segment tree তেও solution possible . আমরা segment tree solution process টা দেখব ।

segment tree এর অনেক প্রবলেম  Data compression করার প্রয়োজন হয় কারণ না হলে রেঞ্জ অনেক বড় হয়ে যায় , প্রথমত এতে segment tree slow হয়ে যাবে যেহেতু অনেক huge range এর মধ্যে কাজ করতে হবে আবার এমনও হতে পারে range এত বড় হয়ে গেল যে ( array size )  আর segment tree develop করা গেল না । Data compression ব্যাপারটা হচ্ছে কোন ভ্যালুকে অন্য কোন ভ্যালু দিয়ে replace করা । ধরি আমাদের দেওয়া আছে  4 , 5 , 101 ৩টা নাম্বার । এখন আমরা যে কাজই করি এই তিনটা নাম্বার দিয়ে করব । এইগুলা কে যদি ইনডেক্স হিসাবে কল্পনা করি তাহলে আমাদের 101 পর্যন্ত নাম্বার access করতে মিনিমাম 101 টা জিনিস লাগবে , কিন্ত্ এইখানে 1-101 এর মধ্যে অনেক কিছুই no use . এখন যদি আমরা 4কে 1 , 5কে 2 , 101 কে 3
দ্বারা কমপ্রেস করি মানে যাই ১ তাই ৪ , যাই ২ তাই ৫ , যাই ৩ তাই ১০১ তাহলে আমরা অপারেশন এবং স্টোরেজ সাইজ দুইটাই কমাইয়া ফেলতে পারছি ।

1. এই প্রবলেমটা জন্য তাই আমরা প্রথমেই  data compression করে নিব । set , map even normal array দিয়েও এই কাজটা সহজেই করা যায় । আমাদের প্রবলেম এর লিমিট থেকে সিন্ধান্ত নিতে হবে আমরা কিভাবে কাজটা করব । 
2. একটা জিনিস খেয়াল করি যদি আমরা শুরু থেকে চিন্তা না করি লাস্ট থেকে চিন্তা করি তাহলে দেখব শেষ এ যে পোস্টারটা লাগানো হয়েছে তা অবশ্যই অবশ্যই দেখা যাবে । এখন শেষ এর দিক দিয়ে সেকেন্ড পোস্টারটা তখনই দেখা যাবে যদি না শেষ পোস্টারটা এসে এইটাকে সম্পূর্ণভাবে কভার করে দেয় । 
3. আমরা তাই শেষ থেকে কাজ করে প্রথমে যাব । segment tree এর সব কিছু true রাখি ( মানে সব পজিশন এখন ভিজিবল ) । তারপর আসতে আসতে প্রতিটা অপারেশন এর সময় শুধু চেক করব যে রেঞ্জ এর মধ্যে এখন পোস্টারটা লাগাব তার কোন একটা পজিশন কি কোন না কোন ভাবে দেখা যায় কিনা , দেখে গেলেই লাস্ট এও এইটা দেখা যাবে কারণ এর পরের পোস্টার গুলা আমরা আগেই লাগাইয়া আসসি ।

কোড 

	const int MX = 1e7 + 10 ;
	const int NX = 40000 + 10 ;
	bool seg[ 8 * NX ] , lazy [ 8 * NX ] ;
	int num[ MX ] , inp[MX][2] , n;
	set < int > s ;
	int lc( int x )
	{
	return 2*x ;
	}
	int rc( int x)
	{
	return ( 2 * x ) + 1 ;
	}
	bool query( int node , int x , int y , int lft , int rgt )
	{
	if( lazy[node] )
	{
	seg[node] = 1;
	lazy[lc(node)] = lazy[node];
	lazy[rc(node)] = lazy[node];
	lazy[node] = 0 ;
	}
	if( x >= lft && y <= rgt ) return seg[node];
	if( x > rgt || y < lft ) return 1 ;
	bool ret = 1 ;
	int mid = ( x + y )/2 ;
	ret &= query( lc(node) , x , mid , lft , rgt );
	ret &= query( rc(node) , mid + 1 , y , lft , rgt );
	return ret ;
	}
	void update( int node , int x , int y , int lft , int rgt )
	{
	if( lazy[node] )
	{
	seg[node] = 1;
	lazy[lc(node)] = lazy[node];
	lazy[rc(node)] = lazy[node];
	lazy[node] = 0 ;
	}
	if( x > rgt || y < lft ) return ;
	if( x >= lft && y <= rgt )
	{
	seg[node] = 1 ;
	if( x != y )
	{
	lazy[lc(node)] = lazy[rc(node)] = 1 ;
	}
	lazy[node] = 0 ;
	return ;
	}
	int mid = ( x + y )/2 ;
	update( lc(node) , x , mid , lft , rgt );
	update( rc(node) , mid + 1 , y , lft , rgt );
	int xx = seg[lc(node)];
	int yx = seg[rc(node)];
	seg[node] = (xx & yx);
	}
	void solve()
	{
	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	s.clear();
	n = II ;
	rep ( i , n )
	{
	int x = II , y = II ;
	s.insert( x ); // ডাটা কমপ্রেশন এর জন্য স্টোর করছি
	s.insert( y ); // ডাটা কমপ্রেশন এর জন্য স্টোর
	inp[i][0] = x ;
	inp[i][1] = y ;
	}
	int idx = 1 ;
	forstl( it , s )
	{
	num[*it] = idx++; // ডামি ভ্যালুগুলা দেওয়া হচ্ছে
	}
	ms( seg , 0 );
	ms( lazy , 0 );
	int i , ans = 0 ;
	for ( i = n - 1 ; i >= 0 ; i-- )
	{
	if( query( 1 , 1 ,idx - 1 , num[inp[i][0]] , num[inp[i][1]] ) == 0 ) // এখনও কমপক্ষে একটা পজিশন খালি আছে যেখান থেকে এই
	// পোস্টারটা দেখা যেতে পারে
	{
	update( 1 , 1 , idx - 1 , num[inp[i][0]] , num[inp[i][1]] );
	ans++;
	}
	}
	printf("%d\n",ans);
	}
	}
	}

view raw seg3.cpp hosted with ❤ by GitHub

এই প্রবলেমটা লাইট ওজি তেও আছে link .  এই সিরিজটা আরো বড় করার ইচ্ছা আছে যদি সময় এবং লিখার মোটিভেশন পাওয়া যায় । ধন্যবাদ পড়ার জন্য ।