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 সব থেকে বেশি হবে । 

কোড ::

রান  টাইম হচ্ছে 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 এর বড় বিলিং করা যায় ( কথাগুলা না বুঝলে ভয় পাওয়ার কিছু নাই কোড দেখলেই বুঝা যাবে ) । 

কোড

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

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 রাখি ( মানে সব পজিশন এখন ভিজিবল ) । তারপর আসতে আসতে প্রতিটা অপারেশন এর সময় শুধু চেক করব যে রেঞ্জ এর মধ্যে এখন পোস্টারটা লাগাব তার কোন একটা পজিশন কি কোন না কোন ভাবে দেখা যায় কিনা , দেখে গেলেই লাস্ট এও এইটা দেখা যাবে কারণ এর পরের পোস্টার গুলা আমরা আগেই লাগাইয়া আসসি ।

কোড 

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