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

ধর, একটি ৫০ ওভারের ক্রিকেট ম্যাচের কোন ওভারে কত রান হয়েছে তা একটি অ্যারে তে স্টোর করা আছে ।এখন যদি জানতে চাওয়া হয় ম্যানডেটরি পাওয়ার প্লে তে(১-১০ ওভার) কত রান এসেছে বা বোলিং/ব্যাটিং পাওয়ার প্লে(ধর,৩৫-৪০ ওভার) তে কত রান এসেছে বা যে কোন একটি রেঞ্জ দিয়ে বলা হয় ঐ রেঞ্জের ওভারে কত রান এসেছে? এটা আমরা খুব সহজেই কিউমুলেটিভ সাম বের করে বলে দিতে পারব।কিন্তু ধর কোন কারণে কোন একটি ওভারের রান টা আপডেট করা লাগবে(হয়ত বলার সময় ভুল হইছিল!😂)।তাহলে কি করব?এখন তো আর কিউমুলেটিভ সাম দিয়ে কাজ হবে না।এরকম ক্ষেত্রে অর্থাৎ যেখানে একটা নির্দিষ্ট রেঞ্জ কুয়েরি করতে হবে এবং আপডেটও থাকবে,সেখানে সেগমেন্ট ট্রি লাগবেই লাগবে।

সেগমেন্ট ট্রি হল একটি ট্রি ডাটা স্ট্রাকচার,যেটা কতগুলো interval/segment কে স্টোর করে রাখে এবং সেখান থেকে একটা নির্দিষ্ট রেঞ্জের মধ্যকার সল্যুশন কুয়েরি করে বের করা যায়।এটা একটা Height Balanced Binary Tree এবং গঠনগতভাবে স্থিতিশীল।এই গাঠনিক স্থিতিশীলতার কারণে এটা Balanced Binary Tree এর চেয়ে কম ইফিশিয়েন্ট,কিন্তু এর রিকার্সিভ অপারেশনের কারণে এটা চিন্তা করা এবং কোড করা অপেক্ষাকৃত সহজ।

সেগমেন্ট ট্রি বুঝতে হলে রিকার্সন সম্পর্কে ভাল ধারণা থাকতে হবে।আর মার্জ সর্ট জানলে সেগমেন্ট ট্রি খুবই সহজ লাগবে।কারণ সেগমেন্ট ট্রি মার্জ সর্টের মতই Divide And Conquer পদ্ধতিতে কাজ করে।


একটা সেগমেন্ট ট্রির সাধারণত তিনটা অপারেশন থাকেঃ
1. Building Tree: To initialize the tree segment/interval
2. Updating Tree: To update the value of given range
3. Query Tree: To retrieve the value of segment/interval

Building Tree:

সেগমেন্ট ট্রি তে আমরা যে সল্যুশন চাই,সেগুলো ট্রির লীফে থাকে।আর সেগুলোর মার্জ করা সল্যুশন ট্রির ইন্টারনাল নোডে থাকে।নিচের ছবিটা দেখি,

                                                                          ছবিঃসংগৃহীত

এটি একটি বাইনারি ট্রি।যেখানে x যদি রুট হয় তাহলে 2*x এবং 2*x+1 হবে তার চাইল্ড।এর k তম লেভেলের ডিসেন্ডেন্ট গুলো 2^k এর (2^(k+1))-1 এর মধ্যে।বাকিটা কোড দেখে বুঝার চেষ্টা করি,

এখানে আমরা ১ কে রুট নোড ধরে শুরু করেছি।ধবি,আমাদের রেঞ্জ a থেকে b।যেহুতু আমাদের ডেটা গুলো লীফে স্টোর করব,তাই যতক্ষন না a=b হবে অর্থ্যাৎ লীফ নোডে না পৌছব তখন ঐ রেঞ্জ টাকে রিকার্সিভ্লি স্প্লিট করতে থাকব।আর লীফে পৌছে গেলেই সেখানে ডেটা tree[] তে স্টোর করে ফাংশন রিটার্ন করে দিব।এবং উপরে উঠার সময় তাদের মার্জ করা করা সল্যুশনও tree[] তে রেখে দিব।

Updating Tree:

আমাদের কুয়েরির মেইন ডেটা গুলো যেহুতু লীফে থাকে,আপডেটও করতে হবে লীফে।আগের মতই রেঞ্জ স্প্লিট করতে করতে যখন আমরা লীফে পৌছে যাব তখন তার সেটার মান আপডেট করে দিব।আর উপরে উঠার সময় ইন্টারনাল নোডের সল্যুশন গুলো মার্জ হয়ে আপডেট হয়ে যাবে।আপডেটের স্যাম্পল কোড টা দেখি,

Query Tree:

কুয়েরি করার সময় আমরা চেক করব বর্তমানে আমরা যে রেঞ্জে আছি সেটা রিলেভেন্ট কি না? অর্থাৎ এখন যে রেঞ্জে আছি তার পুরোটা কুয়েরি রেঞ্জের অন্তর্ভূক্ত হলে সেই নোডের সল্যুশন রিটার্ন করব।আর যদি আংশিকভাবে কুয়েরি রেঞ্জের অনর্ভূক্ত হয় তাহলে রিলেভেন্ট রেঞ্জ পাবার জন্য বর্তমান রেঞ্জকে স্প্লিট করতে থাকব।আর যদি বর্তমান রেঞ্জ পুরোপুরি কুয়েরি রেঞ্জের বাইরে হয় তাহলে এমন একটা ভ্যালু রিটার্ন করব যেন সেটা মেইন সল্যুশনে কোন ইফেক্ট না ফেলে। যেমন যোগফল বের করার সময় 0 রিটার্ন করতে পারি,ম্যাক্সিমাম ভ্যালু বের করার -infinity সময় বা মিনিমাম ভ্যালু বের করার সময় infinity রিটার্ন করতে পারি।কুয়েরি ফাংশনের কোডটা দেখি,

সম্পূর্ন কোডঃ

Complexity:

সেগমেন্ট ট্রি অ্যারে কে বারবার দুই ভাগে ভাগ করে,তাই ট্রি এর ডেপথ হবে log(n)।অতএব,প্রতিটা আপডেট এবং কুয়েরির কমপ্লেক্সিটি O(log n)।সেগমেন্ট ট্রি বিল্ড করার ক্ষেত্রে যেহুতু n টি আপডেট হয়েছে,তাই সেক্ষেত্রে কমপ্লেক্সিটি O(n log n)।

সেগমেন্ট ট্রি শিখা হয়ে গেলে লেজি প্রপাগেশন শিখে নিতে হবে।এটা সেগমেন্ট ট্রির দারুণ একটা অপটিমাইজেশন।

Related Problems & Solution:

1. LightOj 1082 - Array Queries

            Solution: https://ideone.com/3b9GOx

2. LightOj 1112 - Curious Robin Hood
            Solution:https://ideone.com/HPAoJR

Reference:

→http://www.shafaetsplanet.com/planetcoding/?p=1557

→http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html

→http://letuskode.blogspot.in/2013/01/segtrees.html

→http://e-maxx.ru/algo/segment_tree

→https://www.youtube.com/watch?v=ZBHKZF5w4YU