Bitset

মনে কর, তোমাকে একটা অ্যারে a[n] দেয়া আছে যেখানে n<=1e5 এবং a[i]<=1e7।  এরপর তোমাকে q<=1e5 টা কুয়েরী এন্সার করতে হবে। প্রতি কুয়েরী তে একটি সংখ্যা x দিবে। তোমাকে বলতে হবে এই সংখ্যাটি অ্যারে তে আছে কি না? 

এখন এই সমস্যাটির একটি O(n) কমপ্লেক্সিটির সমাধান করতে বলা হলে তুমি কিভাবে করবে? 

এখন, প্রব্লেমের সবকিছু ঠিক রেখে যদি a[i]<=1e9 করে দেয়া হয় তাহলে কী হবে? তোমার সলুশ্যনের মেমোরি কমপ্লেক্সিটি অনেক বেশি হয়ে যাবে। কারণ, প্রতিটি সংখ্যার জন্য তুমি ২বাইট = ১৬ বিট করে মেমোরি নিচ্ছো। 

এখন, এরকম একটা বুলিয়ান অ্যারের পরিবর্তে আমরা বিটসেট ব্যাবহার করতে পারি। আসলে বিটসেটও একটি বুলিয়ান অ্যারে ই। কিন্তু সে প্রতিটি পজিশনের জন্য ১৬ বিট ব্যাবহার না করে মাত্র ১ বিট ব্যাবহার করবে!!! 

তার মানে তোমার উপরোক্ত কোড এর মেমোরি কমপ্লেক্সিটি ১৬ গুণ কমানো সম্ভব!!! 

বিটসেট ব্যাবহার করলে কোড টি নিচের কোডের মতোই হবে। 

এই ছিলো বিটসেটের পরিচয় পর্ব। 

এখন দেখবো বিটসেটের কিছু এপ্লিকেশন।

হ্যাপি কোডিং😊