অ্যাডভান্সড টপিক৮ মিনিট পড়া

মো-এর অ্যালগরিদম (Mo's Algorithm)

রেঞ্জ কুয়েরিগুলোকে (range queries) ক্রমানুসারে উত্তর দেওয়ার বদলে সেগুলোকে বুদ্ধিমানের মতো সাজিয়ে হাজার হাজার কুয়েরির উত্তর দিন

total time:মোট সময়: \(O((n+q)\sqrt{n})\)space:মেমরি বা স্পেস: \(O(n + q)\)requirement:রিকয়ারমেন্ট বা প্রয়োজনীয়তা: শুধুমাত্র অফলাইন — সমস্ত কুয়েরি আগে থেকেই জানা থাকতে হবে

কল্পনা করুন আপনি একজন মিউজিয়ামের পাহারাদার, যার কাজ হলো একটি লম্বা পেইন্টিং বা চিত্রকর্মের নির্দিষ্ট কিছু অংশের ক্ষয়ক্ষতি পরীক্ষা করা। আপনার কাছে পরীক্ষা করার জন্য ১,০০০টি অংশের একটি তালিকা আছে, যার প্রতিটি [l, r] রেঞ্জ (range) বা অঞ্চল কভার করে। আপনি চাইলে প্রতিটি রিকোয়েস্ট বা অনুরোধের জন্য পুরো পেইন্টিংয়ে বাম-থেকে-ডানে হেঁটে যেতে পারেন — কিন্তু এর মানে হলো পুরো রাস্তা ১,০০০ বার ঘোরার সমান।

এর থেকে বুদ্ধিমানের কাজ হলো: রিকোয়েস্টগুলোকে তাদের অবস্থান (location) অনুযায়ী সাজিয়ে নিন (sort), যাতে আপনাকে বারবার পেছনে ফিরে দীর্ঘপথ হাঁটতে না হয়। যদি ১ নম্বর রিকোয়েস্টটি [১০, ৫০] এবং ২ নম্বরটি [১২, ৫৫] রেঞ্জ কভার করে, তবে শুধু আপনার উইন্ডোটিকে প্রথমটি থেকে দ্বিতীয়টিতে স্লাইড (slide) করে নিন বা সরান — এটি মাত্র চারটি ধাপ, ৫৫টি নয়।

এটাই হলো মো-এর অ্যালগরিদম (Mo's Algorithm): রেঞ্জ কুয়েরিগুলোকে একটি নির্দিষ্ট ও চতুর ক্রমানুসারে সাজানোর মাধ্যমে আমরা মোট পয়েন্টারের নড়াচড়াকে (pointer movement) সর্বনিম্ন পর্যায়ে নামিয়ে আনতে পারি এবং অত্যন্ত কার্যকরভাবে (efficiently) সমস্ত কুয়েরির উত্তর দিতে পারি।

স্লাইডিং উইন্ডো (Sliding window) ধারণা

একটি চলন্ত বা স্লাইডিং উইন্ডো [cur_l, cur_r] এবং সেই উইন্ডোর এগ্রিগেট (aggregate) বা সামগ্রিক মান বজায় রাখুন। [l, r] কুয়েরির উত্তর দেওয়ার জন্য, ওই উইন্ডোটিকে কুয়েরির সমান করতে সম্প্রসারিত বা সংকুচিত করুন — একবারে একটি করে এলিমেন্ট বা উপাদান নিয়ে। প্রতিটি প্রসারণ/সংকোচনকে (expansion/contraction) অবশ্যই \(O(1)\) সময়ের মধ্যে এগ্রিগেট বা সামগ্রিক মান আপডেট করতে হবে।

সমস্ত কুয়েরির সম্মিলিত খরচ = পয়েন্টারের মোট মুভমেন্ট বা নড়াচড়া। মো-এর (Mo's) কাজ হলো এই মোট মুভমেন্টকে সর্বনিম্ন পর্যায়ে নামিয়ে আনা।

ব্লক-ভিত্তিক কুয়েরি সর্টিং (Block-based query sorting)

পুরো অ্যারেটিকে B = ⌊√n⌋ সাইজের বিভিন্ন ব্লকে ভাগ করুন। কুয়েরিগুলোকে নিচের নিয়ম অনুযায়ী সাজান (sort):

1. প্রাইমারি কি (Primary key): লেফট বা বামপাশের এন্ডপয়েন্ট (l) যে ব্লকের অন্তর্ভুক্ত সেটি দিয়ে।
2. সেকেন্ডারি কি (Secondary key): রাইট বা ডানপাশের এন্ডপয়েন্ট (r) দিয়ে (জোড়-সংখ্যার ব্লকগুলোর জন্য ছোট থেকে বড় বা ascending অর্ডারে, আর বিজোড়-সংখ্যার ব্লকগুলোর জন্য বড় থেকে ছোট বা descending অর্ডারে — এই "অল্টারনেটিং (alternating)" বা "হিলবার্ট (Hilbert)" ভ্যারিয়েন্টটি ধ্রুবক বা কনস্ট্যান্ট ফ্যাক্টরকে (constant factors) অর্ধেক করে দেয়)।

অ্যালগরিদমের বেসিক সংস্করণে, প্রতিটি ব্লকের ভেতরের সমস্ত কুয়েরিকে রাইট এন্ডপয়েন্ট অনুযায়ী (অ্যাসেন্ডিং বা ascending অর্ডারে) সাজানো হয়। রাইট পয়েন্টারটি ব্লকের ভেতরে শুধু সামনের দিকেই এগোয়। আর যখন পরবর্তী ব্লকে যাওয়া হয়, তখন লেফট পয়েন্টারটি প্রতিটি কুয়েরির জন্য সর্বোচ্চ B সংখ্যক ধাপ যেতে বা লাফাতে (jump) পারে।

কমপ্লেক্সিটি বিশ্লেষণ — √n যেখান থেকে আসে

রাইট পয়েন্টারের মুভমেন্ট: প্রতিটি ব্লকের ভেতরে কুয়েরিগুলোকে r অনুসারে সাজানো থাকে, তাই রাইট পয়েন্টারটি একমুখীভাবে (monotonically) ডানে এগোয় — প্রতি ব্লকের জন্য সর্বোচ্চ n সংখ্যক ধাপ। আর n/B সংখ্যক ব্লকের জন্য, রাইট পয়েন্টারের মোট মুভমেন্ট দাঁড়ায় \(O(n \times n/B)\) = \(O(n^2/B)\)।

লেফট পয়েন্টারের মুভমেন্ট: একটি ব্লকের ভেতরে লেফট পয়েন্টারটি প্রতি কুয়েরির জন্য সর্বোচ্চ 2B = 2√n সংখ্যক ধাপ লাফাতে পারে। q সংখ্যক কুয়েরির জন্য লেফট পয়েন্টারের মোট মুভমেন্ট হবে \(O(q \times B)\)।

মোট খরচ বা মুভমেন্ট = \(O(n^2/B + q\times B)\)। এটার মান তখনই সর্বনিম্ন হবে যখন \(n^2\)/B = q×B → B = n/√q হবে। যখন q ≈ n হয়, তখন অপ্টিমাল B = √n হয়, আর তখন এর মান দাঁড়ায় \(O((n+q)\sqrt{n})\)।

রিকয়ারমেন্টস — যখন মো-এর অ্যালগরিদম কাজ করে না

অফলাইন কুয়েরি: প্রসেসিং বা হিসাব শুরু করার আগেই আপনার সমস্ত কুয়েরি সম্পর্কে জানা থাকতে হবে। আমরা সেগুলোকে পুনরায় সাজিয়ে বা রিঅর্ডার (reorder) করে নিই — আর অনলাইন বা সরাসরি প্রসেসিংয়ে (যেখানে কুয়েরিগুলো একের পর এক আসতে থাকে) আপনি এই কাজ করতে পারবেন না।

সহজ সংযোজন এবং অপসারণ: উইন্ডোর সীমানায় একটি এলিমেন্ট যুক্ত করা (add) বা সেটি থেকে তাকে অপসারণ (remove) করার কাজটি অবশ্যই \(O(1)\) সময়ের মধ্যে হতে হবে। যদি প্রতিটি আপডেটে (update) আপনার এগ্রিগেট বা সামগ্রিক মান \(O(1)\) সময়ের মধ্যে বজায় রাখা না যায়, তবে মো-এর অ্যালগরিদমের (Mo's Algorithm) কোনো সুবিধা আর কাজে আসবে না।

কাউন্ট-ডিস্টিংক্ট এর উদাহরণ (Count-distinct example)

ধরি freq[v] = বর্তমান উইন্ডোতে v ভ্যালুর উপস্থিতির সংখ্যা (count), এবং 'distinct' নামের একটি কাউন্টার (counter)। a[i] এলিমেন্টটি যোগ (add) করা: বৃদ্ধি করার আগে যদি freq[a[i]] == 0 হয় → তারমানে distinct++; তারপর freq[a[i]]++ করুন। a[i] অপসারণ (remove) করা: freq[a[i]]--; কমানোর পর যদি freq[a[i]] == 0 হয় → তারমানে distinct-- করুন। এর দুটি কাজই \(O(1)\) সময়ে সম্পন্ন হয়। যার মোট সময় বা কমপ্লেক্সিটি: \(O((n+q)\sqrt{n})\)।

ট্রি-তে (Trees) মো-এর অ্যালগরিদম

অ্যালগরিদমটির একটি ভ্যারিয়েন্ট (variant) অয়লার ট্যুরের (Euler tour) মাধ্যমে ট্রি-কে রৈখিক (linearize) করে ট্রি-র ওপর পাথ কুয়েরিগুলো (path queries) হ্যান্ডেল বা পরিচালনা করে। এই প্রক্রিয়ায়, লিনিয়ার করা সিকোয়েন্সের ওপর পাথগুলো একেকটি রেঞ্জ কুয়েরিতে পরিণত হয় (যেখানে LCA বা লোয়েস্ট কমন অ্যানসেস্টর-ভিত্তিক সংযোজন/বিয়োজন থাকে)। আর এটির অ্যাসিম্পটোটিক কমপ্লেক্সিটিও একই থাকে।

দ্রষ্টব্য: মো-এর অ্যালগরিদম (Mo's Algorithm) হলো একটি অফলাইন অ্যালগরিদম — আপনি যে ক্রমানুসারে প্রশ্ন বা কুয়েরি করেন, এটি সেই অনুযায়ী উত্তর দিতে রাজি হয় না। এর বদলে মোট কাজের পরিমাণ সর্বনিম্ন করতে এটি আপনার প্রশ্নগুলোকে পুনরায় সাজিয়ে (reorder) নেয়। এটিকে ব্যাচ প্রসেসিংয়ের (batch processing) মতো করে ভাবতে পারেন: প্রথমে আমাকে সব প্রশ্ন একত্রে দিন, আর শেষ আমি দক্ষতার সাথে সবগুলোর সমাধান করে দেব।

মো-এর অ্যালগরিদম (Mo's Algorithm) — রেঞ্জের ভেতরের ইউনিক বা ডিস্টিংক্ট (distinct) এলিমেন্টগুলো গণনা করা

import math
from collections import defaultdict

def mos_count_distinct(arr, queries):
    """
    queries: list of (l, r) pairs (0-indexed, inclusive)
    Returns: list of answers in original query order.
    """
    n = len(arr)
    block = max(1, int(math.isqrt(n)))

    # Sort queries: primary by block of l, secondary by r
    indexed = sorted(enumerate(queries),
                     key=lambda x: (x[1][0] // block,
                                    x[1][1] if (x[1][0] // block) % 2 == 0
                                    else -x[1][1]))

    freq = defaultdict(int)
    distinct = 0
    cur_l, cur_r = 0, -1
    answers = [0] * len(queries)

    def add(idx):
        nonlocal distinct
        if freq[arr[idx]] == 0:
            distinct += 1
        freq[arr[idx]] += 1

    def remove(idx):
        nonlocal distinct
        freq[arr[idx]] -= 1
        if freq[arr[idx]] == 0:
            distinct -= 1

    for qi, (l, r) in indexed:
        while cur_r < r: cur_r += 1; add(cur_r)
        while cur_l > l: cur_l -= 1; add(cur_l)
        while cur_r > r: remove(cur_r); cur_r -= 1
        while cur_l < l: remove(cur_l); cur_l += 1
        answers[qi] = distinct

    return answers

arr = [1, 2, 1, 3, 2, 4]
queries = [(0, 3), (1, 4), (2, 5), (0, 5)]
print(mos_count_distinct(arr, queries))
# [l,r] -> distinct counts: [3, 3, 3, 4]