Data structureIdeaProblem SolvingProgramming

‌প্রোগ্রা‌মিং: সে‌গমেন্ট ট্রি ডাটা স্ট্রাকচার। রেন্জ কু‌য়ে‌রি: যোগফল

Segment tree bangla tutorial

সেগমেন্ট ট্রি একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার। এই ডাটা স্ট্রাকচার টি বিভিন্ন অ্যালগরিদম এ রেঞ্জ অপারেশন চালাতে ব্যবহার করা হয়। আপনারা এমন কিছু প্রব‌লেম দে‌খে থাক‌তে পা‌রেন যেখা‌নে, একটা Array দেয়া থা‌কে N সাইজ এর আর বলা হয় ঐ Array টা‌র উপর Q টি Operation চালা‌তে হ‌বে। প্র‌ত্যেকবার ঐ Array এর i তম index এর মান একটা ভ্যালু V দি‌য়ে আপ‌ডেট কর‌তে হ‌বে প‌রে ঐ Array এর একটা রেন্জ l থে‌কে r এর যোগফল/‌মি‌নিমাম/ম্যা‌ক্সিমাম প্রিন্ট কর‌তে হ‌বে।

সলুশন ১:

প্র‌তিবার Query করার সময় আমরা ঐ Array এর i তম index V দ্বারা Update কর‌বো। প‌রে l থে‌কে r পর্যন্ত যোগফল/‌মি‌নিমাম/ম্যা‌ক্সিমাম বের ক‌রে প্রিন্ট কর‌বো। সহজ হিসাব।

আস‌লে ঝা‌মেলাটা তখনই হয় যখন ঐ প্রব‌লে‌মে নি‌র্দিষ্ট সময় দেয়া থা‌কে। ধরা যাক সময়টা ২ সে‌কেন্ড। তো এখন যা হ‌বে তা হ‌লো N<=10^5,Q<=10^5 হ‌লে সলুশন ১ ২ সে‌কেন্ড এ Answer প্রিন্ট কর‌তে পার‌বে না। তাই সব‌শে‌ষে দেখা যা‌বে আপনার সলুশন TLE খে‌য়ে ব‌সে আ‌ছে। কারন তখন আপনার ঐ ইন‌ডেক্স i এ আপ‌ডেট করার টাইম কম‌প্লে‌ক্সি‌টি হ‌বে O(1) কিন্তু l থে‌কে r রে‌ন্জের SUM/MIN/MAX প্রিন্ট করার কমি‌প্লেক্সি‌টি হ‌বে O(N)। Q টা Query থা‌কে মোট ক‌মপ্লে‌ক্সি‌টি O(N*Q)। এখানেই ঘ‌টে বিপ‌ত্তি। N*Q = 10^10!

সলুশন ২:

এই প্রব‌লেমটা সেগমেন্ট ট্রি (Segment Tree) নামক ডাটা স্ট্রেকচার ব্যবহার ক‌রে খুব সহজেই সমধান করা যায়। শুধু এ ধর‌নের না, আরও অনেক প্রব‌লেম আ‌ছে যা সেগমেন্ট ট্রি ব্যবহার ক‌রে সমাধান সম্ভব। সেগমেন্ট ট্রিতে, আপ‌ডেট ও কু‌য়ে‌রি উভ‌য়েরই ক‌ম‌প্লে‌ক্সি‌টি O(logN) [ 2 base log]। কিন্তু বিল্ড (build) কম‌প্লে‌ক্সি‌টি O(N)।

‌সেগমেন্ট ট্রি কু‌য়ে‌রি অপ‌রেশন। যেখা‌নে সবার শে‌ষের নোড(Leaf Node) গু‌লো Array এর প্র‌তিটা index এর প্র‌তি‌নি‌ধি

‌সেগমেন্ট ট্রি বিল্ড(Build)/‌তৈ‌রি করা:

ছ‌বি ২~: ছ‌বি সূত্র: প্রোগ্র‌া‌মিং ক‌ন্টেস্ট ডেটা স্ট্রাকচার ও অ্যালগ‌রিদম। -‌মো: মাহবুবুল হাসান

N=8 এর জন্য একটা সেগ‌মেন্ট ট্রি এর নকশা উপ‌রের চি‌ত্রে দেখা‌নে হ‌য়ে‌ছে। ধুসর গু‌লো‌কে আপাতত বাদ দেই। আমা‌দের কা‌ছে মোট ৮ টি জায়গা আ‌ছে।

আমরা এখা‌নে রেফা‌রেন্স Array‌ হি‌সে‌বে arr[8] = {1,2,3,4,5,6,7,8} ব্যবহার কর‌বো। N=8, L=0,R=7

Note: এখা‌নে সেগ‌মেন্ট ট্রি এর Tree অ্যারে তে আমরা ১ থে‌কে ই‌ন্ডে‌ক্সিং কর‌বো এবং মূল অ্যারে তে 0 থে‌কে কর‌বো, এবং রিকার্শন সম্প‌র্কে ধারনা ধাক‌তে হ‌বে। মার্জ শর্ট জান‌লে বুঝা সহজ হ‌য়ে যা‌বে।

আমরা যা কর‌বো তা হলো এই জায়গাগু‌লো‌কে আমরা প্রথ‌মে ২ ভা‌গে ভাগ কর‌বো: [1-4] এবং [5-8]। য‌দি আমা‌দের কা‌ছে [L,R] দুই‌টি সীমা থা‌কে ত‌বে এ‌কে দুইভাগ কর‌লে দাড়া‌বে [L,mid] এবং [mid+1,R]। এখা‌নে mid = (L+R)/2 [ইন্টিজার ডি‌ভিশন]।

এভা‌বে আমরা আমা‌দের সীমা‌কে ততক্ষন পর্যন্ত ভাঙ‌তে থাক‌বো যতক্ষন না পর্যন্ত আমা‌দের সেগ‌মে‌ন্টে এক‌টিমাত্র সংখা থা‌কে অর্থাৎ L=R হয়।

 এটা ভাবার কোন কারন নাই যে N, ২ এর ঘাত হ‌লেই এটা সম্ভব। বরং N=3 য‌দি হয় ত‌বে

এখন কথা হ‌লো আমরা তো চি‌ত্রের মাধ্যমে সুন্দর ক‌রে বু‌ঝে ফেল‌তে পা‌রি কিন্তু, এটা‌কে কো‌ডে কর‌বো কিভা‌বে? এবার ছ‌বি ২ এ তাকান। উপ‌রের ধুসর সংখ্যাগু‌লো খেয়াল ক‌‌রেন। এখা‌নে প্র‌তিটা সেগ‌মে‌ন্টের একটি ক‌রে নাম্বার দেয়া হ‌য়ে‌ছে। এ‌দের একটা বিশেষত্ব আ‌ছে। একটা বিষয় দে‌খেন, যে‌কোন সংখ্যা x এর বামে সবসময় 2x এবং ডা‌নে সবসময় 2x+1 থা‌কে। আবার তার প্যা‌রেন্ট হয় x/2. এই টেক‌নিক ব্যবহার ক‌রে খুব সহ‌জেই সেগ‌মেন্ট ট্রি বানা‌নো যা‌বে।

tree[] অ্যারেতে আমরা ট্রি টাকে স্টোর করবো। ট্রি অ্যারের সাইজ হবে ইনপুট অ্যারের 4 গুণ। build ফাংশনটি arr অ্যারে থেকে ট্রি তৈরি করে দিবে। build এর প্যারামিটার হলো L,R,at এখানে at=বর্তমানে কোন নোডে আছি এবং L,R হলো বর্তমানে কোন রেঞ্জে আছি। শুরুতে আমরা নোড ১ এ থাকবো এবং 0-sizeOfarray-1 রেঞ্জে থাকবো(ট্রি এর ছবিটা দেখেন)।

যদি (L==R) হয়ে যায় তাহলে আমরা শেষ নোডে পৌছে গেছি, এখানে যোগফল হবে অ্যারেতে যে ভ্যালু আছে সেটাই, সেটাকে ট্রিতে স্টোর করে রিটার্ণ করে দিলাম। যদি (L==R) না হয় তাহলে অ্যারেটা কে দুই ভাগে ভাগ করতে পা‌রি। বাম পাশের নোডের ইনডেক্স হবে at*2 এবং ডান পাশেরটা at*2+1। এবং অ্যারেটাকে ভাঙবো ঠিক মাঝখানে। এবার রিকার্সিভলি দুই পাশে build কল করলে বাম এবং ডান পাশের ছোটো অংশের যোগফল বের হয়ে যাবে। দুইপাশের কাজ শেষ হয়ে গেলে বর্তমান নোডের যোগফল হবে বাম এবং ডানের নোডের যোগফল।
বুঝতে সমস্যা হলে ট্রি টি খাতায় সিমু‌লেট কর‌লেই সব প‌রিষ্কার হ‌য়ে যা‌বে।

PS: য‌দি বলা থা‌কে কোন সেগ‌মেন্ট এ কত সংখ্যা আ‌ছে ত‌বে আমরা একদম শেষ সেগ‌মে‌ন্টে গি‌য়ে স‌ঠিক সংখ্যা বসা‌বো এবং ফি‌রে এ‌সে স‌ঠিক sum/min/max রাখ‌বো। এই টিউ‌টো‌রিয়া‌লে আমি যোগফল এরটা দেখা‌বো

‌খেয়াল কর‌লে দেখা যায় যে, আমা‌দের প্রথম লে‌ভে‌লে সেগ‌মেন্ট ১ টি, ২য় লেভে‌লে ২ টি, এর প‌রে ৪ টি এভ‌া‌বে ৮,১৬,৩২,N আকা‌রে বাড়‌তে থা‌কে। যা যোগ কর‌লে দঁাড়ায় 2N. সুতরাং আমা‌দের বিল্ড এর ক‌ম‌প্লে‌ক্সি‌টি O(n).

এইবার আমা‌দের কু‌য়ে‌রি কারার একটা ফাংশন দরকার যেটা যে‌কোন রেন্জ l-r এর যোগফল বের ক‌রে দি‌তে পার‌বে।

সেগ‌মেন্ট ট্রি‌তে কু‌য়ে‌রি করা:

ধ‌রেন আমরা যে‌কোন রেন্জ l=0, r=5 (0 index) এর যোগফল চাই। ‌নি‌চের চিত্রটা দে‌খি।

০ থে‌কে ৫ ইন‌ডে‌ক্সের যোগফল বের করার জন্য মার্ক করা অংশগু‌লোর যোগফল বের করাই যথেস্ট।

আমাদের কুয়েরি ফাংশনের কাজ হবে শুধু রিলেভেন্ট নোডগুলোর যোগফল বের করা। কোডটা build ফাংশনের মতোই হবে তবে কিছু কন্ডিশন অ্যাড করতে হবে। ধরেন আপ‌নি এমন একটা নোডে আছো যেখানে bL-eR রেঞ্জের যোগফল আছে। আপ‌নি এই নোডটা রিলেভেন্ট কিনা সেটা কিভাবে বুঝবে? এখানে ৩ ধরণের ঘটনা ঘটতে পারে:

  1. r<bL || eR<r, এখা‌নে সেগ‌মেন্টা পু‌রোপু‌রি বাই‌রের। নেয়ার দরকার নেই। ০ রিটার্ন ক‌রে দি‌বো।
  2. l<=bL&&r>=eR। সেগ‌মেন্টটা রি‌লে‌ভেন্ট। এই নো‌ডের ভ্যালু রিটার্ন দি‌বো।
  3. দুইটার একটাও না, মা‌নে আং‌শিক

 

3 নং কে‌সের জন্য আমরা সেগ‌মেন্ট টা‌কে আরও ভে‌ঙে রি‌লে‌ভেন্ট অংশটুকু নি‌বো।

ট্রি‌তে কু‌য়ে‌রি করার ক‌মপ্লে‌ক্সি‌টি O(log n) প্র‌তিবার কু‌য়ে‌রির শে‌ষ লাই‌নে আমরা দুইটা নোড থে‌কে প্রাপ্ত আউটপুট কলার ফাংশন‌কে দি‌য়ে‌ছি।

ট্রি‌ তে Update আপ‌ডেট করা:

‌ট্রি আপ‌ডেট করা আর বিল্ড করার কোড প্রায় একই। শুধু এখা‌নে একটা শর্ত দি‌য়ে দেয়া আছে। শর্তটা হ‌লো আমা‌দের array তে যে প‌জিশন এ আপ‌ডেট কর‌বো, য‌দি mid এর মান তার থে‌কে বে‌শি হয় ত‌বে আমরা leftNode এ ভি‌জিট কর‌বো, না হ‌লে rightNode এ ভি‌জিট কর‌বো (বিল্ড করার সময় দুইটা‌তেই করতাম)। আপ‌ডেট করা শেষ হ‌লে আমরা নতুন ভ্যালু দি‌য়ে tree এর parent node গু‌লো আপ‌ডেট ক‌রে দি‌বো। এখা‌নে টাইম ক‌ম‌প্লে‌ক্সি‌টি O(log n) । Done! আপ‌ডেট ফংশন

সব মিল‌ি‌য়ে কোডটা দাড়ায় নিম্নরুপ:

 

আমা‌দের কিছু বিষয় জে‌নে রাখতে হ‌বে। প্রথমটা হ‌লো মে‌মো‌রি কম‌প্লে‌ক্সি‌টি। ভূল দৈ‌র্ঘের Array নি‌লে রানটাইম এরর খে‌য়ে যা‌বেন। তাই অ্যা‌রে সাইজ এর ৪ গুন বে‌শি Array Tree হি‌সে‌বে নেওয়াই ভা‌লো। এখা‌নে আরও অনেক লেখা আ‌ছে। আবার য‌দি ব‌লে update এর সময় আমরা array একটা তে আপ‌ডেট না ক‌রে m সংখ্যক কর‌বো। তখন আবার আমা‌দের প্র‌তিটা index এর যে‌তে হ‌বে। তখন এভা‌বে হ‌বে না। TLE খে‌য়ে যে‌তে পা‌রে। এর জন্য Lazy Propagation না‌মের একটা টেক‌নিক ব্যবহার কর‌তে হয়। যা আমরা প‌রে জান‌বো। ঠিক মার্জ সর্টের মতো সেগমেন্ট্রি ট্রিও “ডিভাইড এন্ড কনকোয়ার” পদ্ধতিতে কাজ করে।

লে‌জি প্রপাগেশন টিউটোরিয়াল

আজ‌কের লেখাটা এ পর্যন্তই রাখ‌তে চাই। লেখাটা বড় হওয়ায় ভূল হ‌তে পা‌রে। কারও কোন সমস্যা হ‌লে ক‌মে‌ন্টে জানা‌নোর অনু‌রোধ রই‌লো।

Tags

Related Articles

Close
Close