বাইনারি ইনডেক্সড ট্রি/ফেনউইক(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 পদ্ধতিতে কাজ করে।

ট্রাই(প্রিফিক্স/রেডিক্স ট্রি)

ট্রাই(Trie) হল বহুল ব্যবহৃত একটা ডাটা স্ট্রাকচার।ট্রাই এর সবচেয়ে প্রচলিত প্রয়োগ হল ডিকশনারিতে শব্দ স্টোর করা, সার্চ করা, ডিলিট করা ইত্যাদি।ধরা যাক,ডাটাবেসে বাংলাদেশের সব মানুষের নাম আছে।এখন ডাটাবেস যতই বিশাল হোক না কেন,সেখান থেকে ABUL নামটা খুঁজে বের করতে ৪ টার বেশি অপারেশন লাগবে না(ক্যামনে?😮)।এবার আমরা একটা ওয়েব ব্রাউজারের কথা চিন্তা করি।আমরা যখন ব্রাউজারে সার্চ করার জন্য কিছু লিখি,তখন অনেক টেক্সট অটো কমপ্লিট হয়ে যায় বা যে টেক্সট লিখার পসিবিলিটি আছে তার অনেক গুলো অপশন দেখায়(ক্যামনে বুঝে,আমি কি চায়?😕)। হুম,এইসব ক্ষেত্রে ট্রাই ই হল নাটের গুরু 😉।

ট্রাই(Trie)  হল 'Retrieval' ওয়ার্ড টার একটা Infix।কারণ ট্রাই ডিকশনারি থেকে একটা ওয়ার্ড কে শুধুমাত্র ওয়ার্ডটার একটা প্রিফিক্স দিয়েই খুঁজে বের করতে সক্ষম। Edward Fredkin প্রথমে 'Retrieval' শব্দের এই  Infix নিয়ে এটাকে ট্রি(Tri) বলেন।কিন্তু গ্রাফ থিওরিতে ব্যাপকভাবে প্রচলিত 'ট্রি' থেকে আলাদা করার জন্যই এটাকে ট্রাই বলা হয়ে থাকে।