STL Algorithm

Algorithm Used in Vector

(i) Non-Manipulating Algorithms:

          1. sort(first_iterator,last_iterator)-To sort a given vector.

          2. reverse(first_iterator,last_iterator)-To reverse a given vector.

          3. *max_element(first_iterator,last_iterator)-To find the maximum element of a vector

          4. *min_element(first_iterator,last_iterator)-To find the minimum element of a vector 

          5. accumulate(first_iterator,last_iterator.initial value of sum)-Does the summation of vector elements.

          6. count(first_iterator,last_iterator,x)-Count the occurrence in vector.

          7. find(first_iterator,last_iterator,x)-Points the last address of the vector if the element is not found

বাইনারি ইনডেক্সড ট্রি/ফেনউইক(Fenwick) ট্রি

Related Problems & Solution:

1. LightOj 1112 - Curious Robin Hood
            Solution: http://ideone.com/sIcaHD

লেজি প্রপাগেশন(সেগমেন্ট ট্রি)

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

Updating through Lazy:

নিচের ছবিটা দেখি,

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

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

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

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