Programming Throwdown

এই আর্টিকেলটি পড়ার পূর্বশর্ত: সেগমেন্ট ট্রি, মার্জ সর্ট এলগোরিদম, বাইনারী সার্চ সম্পর্কে ধারণা থাকতে হবে। না থাকলে এই লিংকগুলো থেকে শিখে নাও:-

সেগমেন্ট ট্রি

মার্জ সর্ট

বাইনারী সার্চ

টার্গেট প্রবলেম: আমাদের কাছে একটা অ্যারে আছে। আমাদেরকে কিছু প্রশ্ন করা হবে অ্যারেটা সম্পর্কে। আমাদের সে প্রশ্নগুলোর উত্তর দিতে হবে। প্রশ্নগুলো ৩ টি সংখ্যা \(l\), \(r\) ও \(k\) দেওয়া হবে। আমাদের বলতে হবে অ্যারেটির \(l\) থেকে \(r\) এর মধ্যে \(k\) এর চেয়ে ছোট কয়টি সংখ্যা আছে।

সলিউশান: এটা সলভ করার জন্য আমাদের মনে প্রথমে যে উপায়টা আসতে পারে সেটা হচ্ছে প্রথমে আমরা একটা আলাদা অ্যারেতে এই রেঞ্জ এর সবগুলা সংখ্যা কপি করব, তারপর সর্ট করব, তারপর দেখব কয়টা সংখ্যা k এর চেয়ে ছোট। এভাবে আমরা চাইলে বের করতে পারব। তবে এতে সমস্যা হচ্ছে অনেক সময় লাগবে। প্রতিবার সর্ট করতে ওরস্ট কেস এ টাইম কম্প্লেক্সিটি \(O(log(n))\) হবে । তাই \(q\) টা কুয়েরি হলে মোট টাইম কম্প্লেক্সিটি \(O(qnlog(n))\) হবে। তাই এটা মোটামুটি ধরণের বড় \(q\) এবং \(n\) এর জন্যও অনেক সময় নষ্ট করবে। এটা হলে তো হবে না। এটার টাইম কম্প্লেক্সিটি কমাতে হবে। এজন্য আমরা সেগমেন্ট ট্রির সাহায্য নিব। মূল আইডিয়াটা হচ্ছে সেগমেন্ট ট্রির প্রতিটা নোড এ একটা সংখ্যা সেভ না করে, ওই রেঞ্জ এর সবগুলো সংখ্যা সর্টেড আকারে সেভ করে রাখা হবে। এটার জন্য আমরা মার্জ সর্ট এলগোরিদম এর সাহায্য নেব। মার্জ সর্ট করার সময় আমরা যেভাবে অ্যারেটাকে দুই ভাগে ভাগ করে ফেলি এবং ভাগ করতেই থাকি যতক্ষণ না একটা সংখ্যায় নেমে আসে, এভাবেই কিন্তু আমরা সেগমেন্ট ট্রিও বানাই। সেগমেন্ট ট্রি বানানোর সময়ও আমরা রেঞ্জটাকে দুই ভাগে ভাগ করে ফেলি এবং যতক্ষণ পর্যন্ত না শেষমেশ একটা সংখ্যায় নেমে আসে ততক্ষণ পর্যন্ত ভাগ করতেই থাকি। সেগমেন্ট ট্রি এবং মার্জ সর্ট এর অ্যারে ভাগ করার পদ্ধতিতে আমরা কিন্তু একটা মিল দেখতে পাচ্ছি। এই মিলটাকে ব্যবহার করে আমরা “মার্জ সর্ট” এবং “সেগমেন্ট ট্রি” এর মার্জ করে “মার্জ সর্ট ট্রি” বানাবো। এটা হচ্ছে একটা সেগমেন্ট ট্রি যার প্রত্যেকটা নোডে ওই রেঞ্জ এ মার্জ সর্ট করার পর যে সর্টেড অ্যারেটা তৈরি হয়েছে সেটা থাকবে। এটাকেই মার্জ সর্ট ট্রি বলা হয়। খুবই বেসিক ধারণা। মার্জ সর্ট এবং সেগমেন্ট ট্রি উভয়টা জানা থাকলে মার্জ সর্ট ট্রি বুঝা কোনো ব্যাপার ই না। 🙂

ইমপ্লিমেন্টেশন: ইমপ্লিমেন্টেশনের জন্য আমরা প্রথমে একটি ২ডি ভেক্টর নিব। বিল্ড ফাংশানটা সাধারণ সেগমেন্ট ট্রির বিল্ড ফাংশান এর মতোই হবে। শুধু রেঞ্জ একটি সংখ্যায় নেমে আসলে আমরা ভেক্টরে ভ্যালু এসাইন না করে পুশ করে দিব। আর শেষ লাইনে প্যারেন্ট এর ভেক্টর তৈরি করার জন্য \(merge()\) ফাংশনটি ব্যবহার করব। এটার কাজ তোমরা মার্জ সর্ট এলগোরিদম শিখার সময়ই জেনে এসেছ। 🙂 তাহলেই বিল্ড ফাংশানের কাজ শেষ। এবার আসে আমরা কুয়েরি কিভাবে করব। কুয়েরি করার জন্য আমরা সাধারণ কুয়েরির মতো রেঞ্জটাকে ২ এর পাওয়ারের অনেকগুলা রেঞ্জ এ ভেঙ্গে ফেলব। এ রেঞ্জ এর প্রত্যেকটা নোডের ভেক্টরই কিন্তু আগে থেকে সর্টেড। তাই আমরা বাইনারী সার্চ করে প্রথম সংখ্যাটা বের করব যেটা কুয়েরিতে প্রদত্ত সংখ্যাটার চেয়ে বড়। এটার আগের সবগুলা সংখ্যার সংখ্যাই হবে আমাদের কাঙ্ক্ষিত। এবার আমরা সবগুলা রেঞ্জ এর জন্য এই “সংখ্যাগুলোর সংখ্যার” (মানে কয়টা সংখ্যা আছে এমন) যোগফল বের করে ফেলব। তাহলে এটাই হবে আমাদের কাঙ্ক্ষিত উত্তর।

নিচে এটার সি++ এর কোড দেয়া হল:

বিল্ড ফাংশন:

vector<int>tree[4*N];
int A[N];
void build_tree( int cur , int l , int r )
{
     if( l==r )
     {
            tree[cur].push_back( a[ l ] );
            return ;
     }
     int mid = (l+r)/2;
     build_tree(2*cur, l , mid ); // Build left tree
     build_tree(2*cur+1 , mid+1 , r ); // Build right tree
     tree[cur] = merge( tree[2*cur] , tree[2*cur+1] ); //Merging the two sorted arrays
}

কুয়েরি ফাংশন:

int query( int cur, int l, int r, int x, int y, int k)
{
      if( r < x || l > y )
      {
           return 0; //out of range
      }
      if( x<=l && r<=y )
      {
            //Binary search over the current sorted vector to find elements smaller than K
            return upper_bound(tree[cur].begin(),tree[cur].end(),K)-tree[cur].begin();
      }
      int mid=(l+r)/2;
      return query(2*cur,l,mid,x,y,k)+query(2*cur+1,mid+1,r,x,y,k);
}

কম্প্লেক্সিটি এনালাইসিস:

বিল্ড করার টাইম কম্প্লেক্সিটি হবে \(O(nlogn)\)। এটা আমরা সহজেই অনুধাবন করতে পারি। এখন আসল প্রশ্ন হচ্ছে মেমোরি কম্প্লেক্সিটি কত হবে। আমরা একটু ভাবলেই বুঝতে পারবো যে মেমোরি কম্প্লেক্সিটিও \(O(nlogn)\) হবে। কারণ একটা সংখ্যা সর্বোচ্চ \(logn\) সংখ্যাক বার ট্রি তে থাকতে পারে (ট্রি এর হাইট)।

কুয়েরি ফাংশানের কম্প্লেক্সিটি \(O(log^{2} n)\) হবে। কারণ একটা রেঞ্জ কে সর্বোচ্চ \(logn\) টা ভাগে ভাগ করা যায়। আর প্রতিটা রেঞ্জ এর জন্য একবার করে বাইনারী সার্চ করা লাগবে, যার কম্প্লেক্সিটি \(logn\)। তাই মোট কম্প্লেক্সিটি হবে \(O(log^{2} n)\) 🙂

প্র্যাকটিস প্রবলেমস:

Anton and Permutation KQUERYO এর মাধ্যমেই আমার মার্জ সর্ট ট্রি নিয়ে বিরক্তিকর ক্যাচক্যাচানি শেষ হল। 🙂

একই ক্যাটাগরির নিচের পোস্ট(গুলি) পড়ে দেখতে পারো:

1. SQRT Tree
2. Offline Query Solution Trick
3. Disjoint Set Union (Rank + Path Compression)
4. Disjoint Set Union (Rank Compression)

একই Difficulty এর বাকি পোস্টগুলোর লিস্ট দিয়ে দিচ্ছি, পড়ে দেখতে পারো:

1. Convex Hull
2. Basic Dynamic Programming(Part 1)