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

স্কয়ার রুট ডিকম্পোজিশন (Sqrt Decomposition)

অ্যারেকে √n আকারে ভাগ করুন — প্রতিটা উপাদান চেক করার জন্য খুব বড়, আবার জটিল ট্রি বানানোর জন্য খুব ছোট

build:O(n)range query:O(√n)point update:যোগফলের (sum) জন্য O(1), সর্বনিম্ন/সর্বোচ্চের (min/max) জন্য O(√n)block size:√n

ধরুন আপনি একজন লাইব্রেরিয়ান যিনি ১০,০০০টি বই পরিচালনা করছেন। কোনো একটি প্রশ্নের জন্য প্রতিটি বই খুঁজে দেখতে অনেক সময় লাগবে। কিন্তু যদি আপনি তাদের ১০০টি করে বইয়ের তাক বা শেলফে ভাগ করে রাখেন, তবে আপনি সহজেই পুরো শেলফগুলো স্ক্যান করতে পারবেন এবং র রেঞ্জের (range) কেবল দুই প্রান্তের নির্দিষ্ট বইগুলো চেক করতে পারবেন। আপনি "সব চেক করুন" এর কষ্টের বদলে একটি পরিচালনাযোগ্য O(√n) সুবিধাজনক জায়গা বেছে নিচ্ছেন।

এটিই হলো স্কয়ার রুট ডিকম্পোজিশন (Sqrt Decomposition): আপনার অ্যারেকে B ≈ √n আকারের ব্লকে ভাগ করুন। প্রতিটি ব্লকের জন্য একটি সামগ্রিক বা অ্যাগ্রিগেট (aggregate) মান (যেমন যোগফল, সর্বনিম্ন, XOR, …) প্রি-কম্পিউট (precompute) করে রাখুন। রেঞ্জ কোয়েরিগুলো (range queries) সর্বোচ্চ ২টি আংশিক ব্লকে প্রতিটি উপাদান একে একে চেক করে, এবং মাঝের সম্পূর্ণ ব্লকগুলোর প্রতিটিতে O(1) সময়ে কাজ করে।

স্ট্রাকচার তৈরি করা

n সংখ্যক উপাদানের একটি অ্যারেকে ⌈n/B⌉ সংখ্যক ব্লকে ভাগ করুন, যেখানে B = ⌊√n⌋। প্রতিটি ব্লক b এর জন্য, প্রি-কম্পিউট করুন block[b] = ওই ব্লকের সমস্ত উপাদানের অ্যাগ্রিগেট। এতে একবার অতিক্রম করতে হবে (one pass): সময় লাগবে O(n)। ইনডেক্স i এর উপাদানটি i/B ব্লকের অন্তর্গত।

একটি রেঞ্জ কোয়েরি [l, r] এর উত্তর দেওয়া

এই রেঞ্জটি তিনটি অংশে বিভক্ত:

বাম দিকের আংশিক ব্লক: l কোনো একটি ব্লকের মাঝামাঝি অবস্থিত। ওই ব্লকে l থেকে ব্লকের শেষ পর্যন্ত প্রতিটি উপাদান স্ক্যান করুন (সর্বোচ্চ B−1 টি উপাদান)।

মাঝের সম্পূর্ণ ব্লকগুলো: [l, r] এর মধ্যে সম্পূর্ণভাবে অবস্থিত প্রতিটি ব্লকের জন্য, এর প্রি-কম্পিউট করা অ্যাগ্রিগেট ব্যবহার করুন — প্রতিটি ব্লকের জন্য O(1)।

ডান দিকের আংশিক ব্লক: r এর ব্লকের শুরু থেকে r পর্যন্ত প্রতিটি উপাদান স্ক্যান করুন (সর্বোচ্চ B−1 টি উপাদান)।

মোট কাজ: দুই প্রান্তের আংশিক ব্লকের জন্য O(B) + সম্পূর্ণ ব্লকগুলোর জন্য O(n/B) = O(B + n/B)। B = √n ধরলে এটি সর্বনিম্ন O(√n) এ দাঁড়ায়।

একটি একক উপাদান আপডেট করা (Point update)

i ইনডেক্সের উপাদানটি আপডেট করুন, তারপর ব্লকের অ্যাগ্রিগেট পুনরায় হিসাব করুন:

• যোগফল (Sum): block[i/B] += (new_val − old_val)। সময় লাগে O(1)।
• সর্বনিম্ন/সর্বোচ্চ (Min/Max): নতুন মানটি ব্লকের বর্তমান অ্যাগ্রিগেটের চেয়ে ছোট/বড় হতে পারে, তবে যদি আপনি পুরানো সর্বনিম্ন মানটি বাড়িয়ে থাকেন, তবে পুরো ব্লক পুনরায় স্ক্যান না করে আপনি নতুন সর্বনিম্ন মান বলতে পারবেন না। সময় লাগে O(B) = O(√n)।

লেজি ব্লক (lazy blocks) সহ রেঞ্জ আপডেট

[l, r] এর সমস্ত উপাদানে δ যোগ করতে: সম্পূর্ণ ব্লকগুলোর জন্য O(1) সময়ে lazy[b] += δ সংরক্ষণ করুন — আলাদা আলাদা উপাদানগুলো স্পর্শ করার দরকার নেই। দুই প্রান্তের আংশিক ব্লকগুলোর জন্য, উপাদানগুলো একে একে আপডেট করুন এবং সেই ব্লকগুলোর অ্যাগ্রিগেট পুনরায় হিসাব করুন। মোট সময়: O(√n)। যখন কোয়েরিগুলো কোনো ব্লকে পৌঁছায় বা এর নির্দিষ্ট উপাদানগুলো স্ক্যান করে, তখন তারা এই লেজি মানটি যুক্ত করে নেয়।

কখন স্কয়ার রুট ডিকম্পোজিশন ব্যবহার করবেন

একটি সেগমেন্ট ট্রি (segment tree) O(log n) সময়ে কোয়েরি এবং আপডেট করে — যা O(√n) এর চেয়ে দ্রুত। কিন্তু স্কয়ার রুট ডিকম্পোজিশন ইমপ্লিমেন্টেশনের সরলতা (implementation simplicity) এর ক্ষেত্রে এগিয়ে থাকে: কোনো ট্রি স্ট্রাকচার নেই, রিকার্সিভ লেজি প্রপাগেশন (recursive lazy propagation) নেই, শুধু কিছু অ্যারে সাধারণ গাণিতিক হিসাব। নির্দিষ্ট কিছু জটিল অ্যাগ্রিগেটস (যেমন কিছু "শেষ উপস্থিতি" বা "last occurrence" কোয়েরি) যা সেগমেন্ট ট্রিতে করা কঠিন, স্কয়ার রুট ডিকম্পোজিশন সেখানে সহজেই মানিয়ে নেয়। প্রতিযোগিতামূলক প্রোগ্রামিংয়ে (competitive programming), যেখানে একটি সেগমেন্ট ট্রির সঠিক কোড লিখতে ৩০ মিনিট লাগতে পারে, সেখানে স্কয়ার রুট ডিকম্পোজিশন মাত্র ১০ মিনিট নেয়।

দ্রষ্টব্য: √n ট্রিক বা কৌশলটি অনেক অ্যালগরিদমে দেখা যায়: মো-এর অ্যালগরিদম (Mo's Algorithm) কোয়েরিগুলোকে √n এর ব্লকে সাজায়, হেভি-লাইট ডিকম্পোজিশন (Heavy-Light Decomposition) O(√n) দৈর্ঘ্যের O(log n) টি চেইন তৈরি করে, এবং স্কয়ার রুট ডিকম্পোজিশন সরাসরি √n এর ব্লক ব্যবহার করে। যখনই আপনি O(√n) দেখবেন, বুঝতে হবে কেউ সমতুল্য O(n) আকারের দুটি জিনিসের মধ্যে ভারসাম্য বজায় রাখার চেষ্টা করছে।

স্কয়ার রুট ডিকম্পোজিশন — পয়েন্ট আপডেট সহ রেঞ্জ সাম

import math

class SqrtDecomp:
    def __init__(self, arr):
        self.arr = arr[:]
        self.n = len(arr)
        self.B = max(1, int(math.isqrt(self.n)))
        num_blocks = (self.n + self.B - 1) // self.B
        self.blocks = [0] * num_blocks
        for i, v in enumerate(arr):
            self.blocks[i // self.B] += v

    def update(self, i, val):
        self.blocks[i // self.B] += val - self.arr[i]
        self.arr[i] = val

    def query(self, l, r):  # inclusive [l, r]
        total = 0
        bl, br = l // self.B, r // self.B
        if bl == br:
            return sum(self.arr[l:r+1])
        # Left partial block
        total += sum(self.arr[l : (bl+1)*self.B])
        # Full middle blocks
        for b in range(bl+1, br):
            total += self.blocks[b]
        # Right partial block
        total += sum(self.arr[br*self.B : r+1])
        return total

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
sq = SqrtDecomp(arr)
print(sq.query(2, 7))  # 5+7+9+11+13+15 = 60
sq.update(4, 0)        # arr[4] = 0 (was 9)
print(sq.query(2, 7))  # 5+7+0+11+13+15 = 51