Sparse table, sqrt decomposition আর Mo’s algorithm

১ · স্থির অ্যারে, হাজারো প্রশ্ন

কারওয়ান বাজারের একজন চালের আড়তদার গত এক বছরের প্রতিদিনের মোটা চালের কেজিপ্রতি দাম একটি খাতায় লিখে রেখেছেন — ৩৬৫টি সংখ্যা। খাতাটি আর বদলাবে না; পুরোনো দিনের দাম তো আর পাল্টায় না। কিন্তু প্রশ্ন আসতেই থাকে: “ফেব্রুয়ারির ১০ থেকে মার্চের ২০ পর্যন্ত সবচেয়ে কম দাম কত ছিল?”, “রমজানের মাসে সর্বোচ্চ দাম কত?”, “বর্ষার তিন মাসে?” একটি গবেষণা প্রতিষ্ঠান হয়তো এমন লাখো প্রশ্ন করবে, বিভিন্ন জেলার, বিভিন্ন পণ্যের।

এটিই range query-এর সমস্যা, আর এই পর্বের বিশেষ শর্তটি হলো: অ্যারেটি স্থির (static) — কোনো আপডেট নেই। প্রতিটি প্রশ্নে l থেকে r পর্যন্ত হেঁটে উত্তর বের করা যায়, কিন্তু সেটি প্রতি প্রশ্নে O(n). n = 10⁶ দিনের ডেটা আর q = 10⁶ প্রশ্নে প্রায় 10¹² ধাপ — অচল। উল্টো দিকে, সব সম্ভাব্য (l, r) জোড়ার উত্তর আগে থেকে লিখে রাখলে প্রশ্ন O(1), কিন্তু জোড়া প্রায় n²/2 টি — 10⁶ দিনে ৫০,০০০ কোটি ঘর, কোনো মেমরিতে ধরবে না। আমাদের দরকার মাঝামাঝি কিছু: অল্প প্রস্তুতি, দ্রুত উত্তর।

যোগফলের জন্য prefix sum — কিন্তু min-এর জন্য নয়

পর্ব ১৭-এ আপনি prefix sum দেখেছেন: P[i] = প্রথম i টি মানের যোগফল, আর sum(l, r) = P[r + 1] − P[l]. প্রস্তুতি O(n), প্রতিটি প্রশ্ন O(1) — নিখুঁত। কিন্তু এই কৌশলের পেছনে একটি লুকানো শর্ত আছে: যোগের একটি উল্টো অপারেশন (বিয়োগ) আছে। বড় অংশের যোগফল থেকে বাড়তি অংশের যোগফল বাদ দেওয়া যায়।

সর্বনিম্নের (min) ক্ষেত্রে এমন কোনো উল্টো নেই। ধরুন জানেন প্রথম ১০০ দিনের সর্বনিম্ন দাম ৪২ টাকা, আর প্রথম ৫০ দিনের সর্বনিম্নও ৪২ টাকা। তাহলে ৫১ থেকে ১০০ দিনের সর্বনিম্ন কত? জানা সম্ভব নয় — ৪২-ও হতে পারে, ৫৫-ও হতে পারে। “বাদ দেওয়া” যায় না। তাই min আর max-এর জন্য prefix কৌশল ভেঙে পড়ে, আর আমাদের একটি নতুন ধারণা দরকার। এই পর্বে তিনটি কৌশল দেখব, তিনটি ভিন্ন দর্শন নিয়ে:

আগের তিনটি পর্বে (৩৪–৩৬) আপনি segment tree আর Fenwick tree দেখেছেন — সেগুলো আপডেটসহ প্রতিটি কাজ O(log n)-এ করে। তাহলে এই পর্বের কৌশলগুলো কেন? কারণ প্রতিটি কোনো একটি দিক থেকে তাদের হারায়: sparse table প্রশ্নে দ্রুততর (O(1) বনাম O(log n)), sqrt অনেক বেশি নমনীয় আর লিখতে সহজ, আর Mo এমন প্রশ্নের উত্তর দেয় যা segment tree-তে সহজে জোড়া যায় না। পর্বের শেষে একটি তুলনার টেবিলে সব একসাথে রাখব।

২ · Sparse table — দুইয়ের ঘাতের দৈর্ঘ্যে উত্তর জমিয়ে রাখা

মূল ধারণাটি সহজ: সব (l, r) জোড়ার উত্তর রাখা অসম্ভব, কিন্তু শুধু সেই অংশগুলোর উত্তর রাখুন যাদের দৈর্ঘ্য 1, 2, 4, 8, 16, … — দুইয়ের ঘাত। প্রতিটি শুরুর অবস্থান i-র জন্য এমন দৈর্ঘ্য মাত্র ⌊log₂ n⌋ + 1 টি। তাই মোট ঘর প্রায় n log n — 10⁶ উপাদানে প্রায় দুই কোটি, যা মেমরিতে ধরে।

পরের সারিগুলো বানাতে আবার পুরো অংশ ঘুরতে হয় না। 2^k দৈর্ঘ্যের একটি অংশকে ঠিক মাঝখানে কাটলে দুটি 2^k−1 দৈর্ঘ্যের অংশ পাওয়া যায়, আর তাদের উত্তর আগের সারিতে আগেই আছে:

এটি আসলে একটি ছোট dynamic programming: বড় সমস্যার উত্তর দুটি ছোট, আগে সমাধান করা সমস্যা থেকে। প্রতিটি ঘর O(1)-এ ভরে। নিচের ডায়াগ্রামে আটটি দিনের দাম (a = 5, 2, 4, 7, 1, 3, 6, 8) দিয়ে পুরো টেবিলটি বানানো দেখুন:

Pseudocode — sparse table build (0-based, rows k = 0 .. LOG)

LOG = floor(log2(n))
for i = 0 to n-1:          st[0][i] = a[i]
for k = 1 to LOG:
    for i = 0 to n - 2^k:  st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)])

জটিলতার হিসাব নিখুঁতভাবে: সারি k-তে n − 2^k + 1 টি ঘর, k = 0 থেকে ⌊log₂ n⌋ পর্যন্ত। যোগফল ≤ n(⌊log₂ n⌋ + 1), আর k ≤ ⌊log₂ n⌋ − 1 সারিগুলোর প্রতিটিতে অন্তত n/2 টি ঘর — তাই Θ(n log n) সময়, আর একই পরিমাণ জায়গা। লুপের ক্রম লক্ষ করুন: বাইরের লুপ k, ভেতরের লুপ i. উল্টো করলে st[k−1][i + 2^(k−1)] তখনো তৈরি না-ও হতে পারে।

৩ · O(1)-এ সর্বনিম্ন — দুটি ওভারল্যাপ করা ব্লক

এখন প্রশ্ন [l, r] (দুই প্রান্তসহ)। এর দৈর্ঘ্য len = r − l + 1 সাধারণত দুইয়ের ঘাত নয় — যেমন ৫. কৌশলটি: সবচেয়ে বড় দুইয়ের ঘাত 2^k নিন, যা len-এর চেয়ে বড় নয় (k = ⌊log₂ len⌋). এরপর দুটি ব্লক:

• ব্লক A: l থেকে শুরু, দৈর্ঘ্য 2^k — st[k][l]
• ব্লক B: r-এ শেষ, দৈর্ঘ্য 2^k — শুরু r − 2^k + 1, তাই st[k][r − 2^k + 1]

উত্তর = min(A, B). মাত্র দুটি ঘর পড়া, একটি তুলনা — O(1), len যত বড়ই হোক।

প্রমাণ — দুটি ব্লক কেন ঠিক পুরো রেঞ্জটি ঢাকে

দাবি: k = ⌊log₂ len⌋ হলে ব্লক A = [l, l + 2^k − 1] আর B = [r − 2^k + 1, r]-এর মিলন ঠিক [l, r].

যুক্তি: k-এর সংজ্ঞায় 2^k ≤ len < 2^k+1. (ক) দুটি ব্লকই রেঞ্জের ভেতরে: A শেষ হয় l + 2^k − 1 ≤ l + len − 1 = r-এ, আর B শুরু হয় r − 2^k + 1 ≥ r − len + 1 = l-এ। (খ) মাঝে কোনো ফাঁক নেই: A-র পরের ঘর l + 2^k, আর B শুরু r − 2^k + 1 = l + len − 2^k. যেহেতু len < 2 · 2^k, তাই l + len − 2^k < l + 2^k — B শুরু হয় A শেষ হওয়ার আগেই বা ঠিক পরে। তাই [l, r]-এর প্রতিটি ঘর অন্তত একটি ব্লকে, আর বাইরের কোনো ঘর কোনো ব্লকে নেই। min-এর জন্য min(A ∪ B) = min(min A, min B), ওভারল্যাপ থাকলেও। ∎

Idempotent অপারেশন — কোন প্রশ্নে O(1) চলে

শেষ বাক্যটিতেই সব: একটি ঘর দুবার নিলেও উত্তর বদলায় না। যে অপারেশনে f(x, x) = x, তাকে বলে idempotent operation. সাথে লাগে associativity (কোন ক্রমে জোড়া হলো তাতে কিছু যায় আসে না)। এই দুই শর্ত মানে এমন অপারেশন:

যোগ আর XOR-এর জন্য অবশ্য prefix কৌশলই ভালো (O(1)), কারণ তাদের উল্টো আছে। Sparse table-এর আসল জায়গা তাই ঠিক যেখানে prefix ব্যর্থ: min, max, gcd — উল্টো নেই, কিন্তু idempotent.

log আগে থেকে হিসাব করে রাখা

প্রতিটি প্রশ্নে k = ⌊log₂ len⌋ লাগে। floating-point-এর log2() ফাংশন ধীর, আর 2^k-এর ঠিক কাছে rounding-এর ভুলে এক কম বা বেশি দিতে পারে — off-by-one-এর ক্লাসিক উৎস। নিরাপদ উপায়: একটি ছোট অ্যারে আগে থেকে বানান, lg[1] = 0 আর lg[x] = lg[x / 2] + 1, O(n)-এ। C++20-এ বিকল্প std::bit_width(len) − 1 (বা GCC-র __lg(len)), Python-এ len.bit_length() − 1 — দুটিই পূর্ণসংখ্যার হিসাব, তাই নির্ভুল।

পুরো কোড — sparse table, brute force-এর সাথে মিলিয়ে

নিচের প্রোগ্রাম ওপরের অ্যারের টেবিল ছাপে, চারটি প্রশ্নের উত্তর দেয়, তারপর ২০০টি এলোমেলো অ্যারেতে মোট ৪,০০০টি এলোমেলো প্রশ্নে sparse table-এর উত্তর সরাসরি হেঁটে বের করা উত্তরের (brute force) সাথে মেলায় — এটিই stress testing. এলোমেলো সংখ্যা আসে একটি ছোট নিজস্ব জেনারেটর থেকে (linear congruential), যাতে C++ আর Python ঠিক একই ইনপুট পায়।

#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
struct SparseMin {
    vector<int> lg;                          // lg[x] = floor(log2 x)
    vector<vector<int>> st;                  // st[k][i] = min of a[i .. i + 2^k - 1]
    SparseMin(const vector<int>& a) {
        int n = a.size(); lg.assign(n + 1, 0);
        for (int x = 2; x <= n; ++x) lg[x] = lg[x / 2] + 1;
        st.assign(lg[n] + 1, {}); st[0] = a;
        for (int k = 1; k <= lg[n]; ++k)
            for (int i = 0; i + (1 << k) <= n; ++i)
                st[k].push_back(min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]));
    }
    int query(int l, int r) const {          // inclusive [l, r], O(1)
        int k = lg[r - l + 1]; return min(st[k][l], st[k][r - (1 << k) + 1]);
    }
};
unsigned long long seed = 12345;
int rnd(int m) { seed = (seed * 1103515245 + 12345) % 2147483648ULL; return int(seed % m); }
int main() {
    vector<int> a = {5, 2, 4, 7, 1, 3, 6, 8};
    SparseMin s(a);
    for (size_t k = 0; k < s.st.size(); ++k) {
        printf("k=%zu:", k); for (int x : s.st[k]) printf(" %d", x); printf("\n");
    }
    for (auto [l, r] : vector<pair<int, int>>{{0, 2}, {2, 6}, {5, 7}, {3, 3}}) printf("min[%d,%d] = %d\n", l, r, s.query(l, r));
    int bad = 0, tests = 0;
    for (int t = 0; t < 200; ++t) {                  // stress test against brute force
        vector<int> b(1 + rnd(50));
        for (int& x : b) x = rnd(100);
        SparseMin sb(b);
        for (int q = 0; q < 20; ++q, ++tests) {
            int l = rnd(b.size()), r = rnd(b.size()); if (l > r) swap(l, r);
            bad += sb.query(l, r) != *min_element(b.begin() + l, b.begin() + r + 1);
        }
    }
    printf("random queries: %d, mismatches: %d\n", tests, bad);
}

k=0: 5 2 4 7 1 3 6 8
k=1: 2 2 4 1 1 3 6
k=2: 2 1 1 1 1
k=3: 1
min[0,2] = 2
min[2,6] = 1
min[5,7] = 3
min[3,3] = 7
random queries: 4000, mismatches: 0

class SparseMin:
    def __init__(self, a):
        n = len(a)
        self.lg = [0] * (n + 1)              # lg[x] = floor(log2 x)
        for x in range(2, n + 1):
            self.lg[x] = self.lg[x // 2] + 1
        self.st = [a[:]]                     # st[k][i] = min of a[i .. i + 2^k - 1]
        for k in range(1, self.lg[n] + 1):
            prev, h = self.st[k - 1], 1 << (k - 1)
            self.st.append([min(prev[i], prev[i + h]) for i in range(n - (1 << k) + 1)])

    def query(self, l, r):                   # inclusive [l, r], O(1)
        k = self.lg[r - l + 1]
        return min(self.st[k][l], self.st[k][r - (1 << k) + 1])

a = [5, 2, 4, 7, 1, 3, 6, 8]
s = SparseMin(a)
for k, row in enumerate(s.st):
    print(f"k={k}:", *row)
for l, r in [(0, 2), (2, 6), (5, 7), (3, 3)]:
    print(f"min[{l},{r}] = {s.query(l, r)}")

seed = 12345
def rnd(m):                                  # same LCG as the C++ version
    global seed
    seed = (seed * 1103515245 + 12345) % 2147483648
    return seed % m

bad = tests = 0
for t in range(200):                         # stress test against brute force
    b = [rnd(100) for _ in range(1 + rnd(50))]
    sb = SparseMin(b)
    for q in range(20):
        l, r = sorted((rnd(len(b)), rnd(len(b))))
        bad += sb.query(l, r) != min(b[l:r + 1])
        tests += 1
print(f"random queries: {tests}, mismatches: {bad}")

k=0: 5 2 4 7 1 3 6 8
k=1: 2 2 4 1 1 3 6
k=2: 2 1 1 1 1
k=3: 1
min[0,2] = 2
min[2,6] = 1
min[5,7] = 3
min[3,3] = 7
random queries: 4000, mismatches: 0

৪ · RMQ-এর প্রয়োগ — LCA থেকে suffix array পর্যন্ত

“একটি রেঞ্জের সর্বনিম্ন” — প্রশ্নটি নিরীহ শোনায়, কিন্তু range minimum query (RMQ) অ্যালগরিদমের জগতে একটি কেন্দ্রীয় হাতিয়ার, কারণ অনেক আপাত-ভিন্ন সমস্যা এতে রূপান্তরিত হয়। প্রায়ই সর্বনিম্ন মানের বদলে তার অবস্থান (index) দরকার হয় — তখন টেবিলে index রাখুন আর তুলনা করুন a[x] < a[y] দিয়ে।

LCA — tree-র প্রশ্নকে অ্যারের প্রশ্নে বদলানো

একটি tree-তে দুটি node u আর v-এর lowest common ancestor (LCA) হলো সবচেয়ে গভীর node, যে দুজনেরই পূর্বপুরুষ। একটি পরিবারের বংশতালিকায় “দুই চাচাতো ভাইয়ের সবচেয়ে কাছের সাধারণ দাদা কে?” — এই প্রশ্ন। পর্ব ৪৮-এ binary lifting দিয়ে এর O(log n) সমাধান দেখবেন; এখানে একটি ঝলক, কীভাবে sparse table একে O(1) করে।

Tree-তে root থেকে DFS চালান, আর প্রতিটি node-এ ঢোকার সময় এবং প্রতিটি সন্তান থেকে ফিরে আসার সময় সেই node-টি লিখে রাখুন। এই ক্রমটির নাম Euler tour; n টি node-এ এর দৈর্ঘ্য 2n − 1. প্রতিটি অবস্থানে node-এর গভীরতাও লিখুন। ধরুন root 0-এর দুই সন্তান 1 আর 2, আর 1-এর দুই সন্তান 3 আর 4:

pos   : 0  1  2  3  4  5  6  7  8
node  : 0  1  3  1  4  1  0  2  0
depth : 0  1  2  1  2  1  0  1  0

first[3] = 2, first[4] = 4  -> min depth on [2, 4] at pos 3 -> LCA(3, 4) = 1
first[3] = 2, first[2] = 7  -> min depth on [2, 7] at pos 6 -> LCA(3, 2) = 0

কেন কাজ করে? u থেকে v-তে DFS যে পথে হাঁটে, তা u আর v-এর LCA-র ওপর দিয়ে যায়, কিন্তু LCA-র ওপরে কখনো ওঠে না — কারণ LCA-র subtree থেকে বেরোনোর আগেই v-তে পৌঁছানো যায়। তাই first[u] থেকে first[v]-এর মধ্যে সবচেয়ে কম গভীরতার node-টিই LCA. Euler tour বানাতে O(n), গভীরতার অ্যারেতে sparse table O(n log n), তারপর প্রতিটি LCA প্রশ্ন O(1). হাজার হাজার LCA প্রশ্নের সমস্যায় (যেমন tree-তে দুই node-এর দূরত্ব = depth[u] + depth[v] − 2·depth[LCA]) এটি খুব কাজের।

আরও কিছু RMQ

• Suffix array-তে LCP: পর্ব ৫৯-এ দেখবেন, দুটি suffix-এর longest common prefix = LCP অ্যারের একটি রেঞ্জের সর্বনিম্ন। String-এর বহু প্রশ্ন এভাবে O(1)-এ।
• Sliding window-এর সর্বনিম্ন: সব জানালা একই দৈর্ঘ্যের হলে monotonic deque (পর্ব ১৬) O(n)-এ যথেষ্ট; কিন্তু জানালার দৈর্ঘ্য প্রশ্নভেদে আলাদা হলে sparse table.
• উত্তরের ওপর binary search: “l থেকে শুরু করে সবচেয়ে লম্বা কোন অংশের gcd এখনো ১-এর বেশি?” — gcd যত ডানে যাবেন ততই কমে বা একই থাকে (monotonic), তাই r-এর ওপর binary search (পর্ব ১৯), প্রতিটি পরীক্ষা sparse table-এ O(1).

৫ · Sqrt decomposition — √n আকারের ব্লক

Sparse table দ্রুত, কিন্তু একটি দুর্বলতা মারাত্মক: একটি মান বদলালেই অনেক ঘর বদলাতে হয়। a[p] যে যে অংশে আছে, তাদের সবাই — সারি k-তে 2^k টি পর্যন্ত, সব সারি মিলে প্রায় 2n টি। একটি আপডেট O(n). তাই আড়তদার যদি প্রতিদিন নতুন দাম যোগ করেন বা পুরোনো ভুল সংশোধন করেন, আমাদের অন্য কিছু লাগবে।

এটিই sqrt decomposition. অ্যারেকে B আকারের ব্লকে ভাগ করুন (শেষ ব্লক ছোট হতে পারে); উপাদান i আছে ব্লক ⌊i / B⌋-তে। প্রতিটি ব্লকের একটি সারাংশ রাখুন — যোগফল, সর্বনিম্ন, বা যা দরকার। B = √n হলে ব্লক প্রায় √n টি, প্রতিটিতে প্রায় √n টি উপাদান।

Pseudocode — sqrt decomposition, range sum (0-based, inclusive [l, r])

build:   for i = 0 to n-1:  sum[i / B] += a[i]                 // O(n)
query(l, r):
    s = 0
    while l <= r and l % B != 0:  s += a[l];  l += 1          // left partial block
    while l + B - 1 <= r:         s += sum[l / B];  l += B    // full blocks
    while l <= r:                 s += a[l];  l += 1          // right partial block
    return s
update(i, v):  sum[i / B] += v - a[i];  a[i] = v              // O(1)

জটিলতা: প্রশ্নে দুই প্রান্তে মোট সর্বোচ্চ 2(B − 1) টি ঘর আর মাঝে সর্বোচ্চ ⌈n / B⌉ টি ব্লক — O(B + n/B). B = √n হলে O(√n). যোগফলের point update O(1), min/max-এর point update O(B) = O(√n). জায়গা: অ্যারে ছাড়া মাত্র O(n/B) = O(√n) বাড়তি। n = 10⁵-এ √n ≈ 316, তাই একটি প্রশ্নে প্রায় ৯০০টি ধাপ — log₂ n ≈ 17-এর চেয়ে অনেক বেশি, কিন্তু 10⁵ প্রশ্নে মোট প্রায় 10⁸ সরল ধাপ, যা সাধারণত এক সেকেন্ডের কাছাকাছি সময়ে চলে।

৬ · রেঞ্জ আপডেট, ব্লকের মাপ আর কখন sqrt জেতে

রেঞ্জ আপডেট — ব্লকের গায়ে “বাকি কাজ” লিখে রাখা

এখন আপডেটও একটি রেঞ্জে: “ঘর l থেকে r পর্যন্ত সবার সাথে v যোগ করুন” (range update) — যেমন একটি এলাকার সব দোকানে ভ্যাট বাড়লে সব দামে একই পরিমাণ যোগ। প্রতিটি ঘর বদলালে O(n). প্রশ্নের মতোই ভাগ করুন: দুই প্রান্তের অসম্পূর্ণ ব্লকে ঘর ধরে ধরে যোগ করুন (আর সেই ব্লকের সারাংশও হালনাগাদ), কিন্তু মাঝের প্রতিটি পূর্ণ ব্লকে শুধু একটি সংখ্যা লিখে রাখুন: lazy[b] += v — “এই ব্লকের সবার সাথে v যোগ হওয়ার কথা, এখনো করা হয়নি”. এটিই lazy propagation-এর সরলতম রূপ (segment tree-তে এর পূর্ণ রূপ পর্ব ৩৫-এ)।

Pseudocode — range add, range sum with block lazy values (0-based)

add(l, r, v):
    for each i in a partial block:   a[i] += v;  sum[i / B] += v
    for each full block b:           lazy[b] += v
query(l, r):
    partial cell i contributes       a[i] + lazy[i / B]
    full block b contributes         sum[b] + lazy[b] * (size of block b)

দুটি কাজই O(B + n/B) = O(√n). সর্বনিম্নের রেঞ্জ-যোগেও একই কৌশল চলে, কারণ সবার সাথে v যোগ করলে min-ও ঠিক v বাড়ে: পূর্ণ ব্লকের উত্তর mn[b] + lazy[b]. কিন্তু অসম্পূর্ণ ব্লকে কিছু ঘর বদলালে সেই ব্লকের mn আবার হিসাব করতে হয় (O(B)) — আর তার আগে সেই ব্লকের lazy মান ঘরগুলোতে নামিয়ে দেওয়া সহজ নিয়ম। “রেঞ্জের সব মান x-এ বসাও” (assign) ধরনের আপডেটেও একই ধারণা, শুধু lazy-তে যোগের বদলে একটি “বসানো মান” রাখুন।

ব্লকের মাপ বেছে নেওয়া — দুই খরচের ভারসাম্য

B = √n কেন? একটি প্রশ্নের খরচ প্রায় f(B) = B + n/B (প্রান্তে B পর্যন্ত, মাঝে n/B পর্যন্ত)। B ছোট হলে ব্লক অনেক — মাঝের অংশ দামি; B বড় হলে প্রান্ত দামি। AM–GM অসমতা বলে B + n/B ≥ 2√n, আর সমতা ঠিক B = √n-এ। (ক্যালকুলাসে: f′(B) = 1 − n/B² = 0.)

কিন্তু খরচ সবসময় এমন প্রতিসম নয়। ধরুন u টি min-এর point update (প্রতিটি O(B), ব্লক নতুন করে হিসাব) আর q টি প্রশ্ন (প্রতিটি O(B + n/B)). মোট ≈ (u + q)B + qn/B; ভারসাম্যে B = √(qn / (u + q)). প্রায় সবই আপডেট হলে B ছোট রাখুন; প্রায় সবই প্রশ্ন হলে B = √n-এর কাছে। বাস্তবে আরও দুটি কথা: (১) ধ্রুবক গুণক — প্রান্তের ঘর-পড়া খুব সস্তা আর cache-বান্ধব, ব্লকের সারাংশ পড়া একটু কম, তাই কখনো √n-এর চেয়ে কিছুটা বড় B দ্রুততর হয়; (২) B-কে দুইয়ের ঘাত (যেমন 256 বা 512) নিলে i / B একটি shift-এ হয়। প্রতিযোগিতায় সাধারণ অভ্যাস: n = 10⁵-এ B ≈ 300–400, তারপর মেপে দেখা।

কখন sqrt log-এর স্ট্রাকচারকে হারায়

O(√n) কাগজে O(log n)-এর চেয়ে খারাপ, তবু sqrt decomposition কনটেস্ট আর বাস্তবে টিকে আছে তিনটি কারণে:

• সরলতা: দশ-পনেরো লাইনে লেখা যায়, ভুলের জায়গা কম। সময়ের চাপে segment tree-র lazy-র ভুলের চেয়ে sqrt-এর একটি পরিষ্কার সমাধান প্রায়ই নিরাপদ।
• নমনীয় অপারেশন: segment tree-তে দুটি সন্তানের উত্তর জুড়ে বাবার উত্তর বানাতে পারতে হয়। কিন্তু “রেঞ্জে x-এর চেয়ে ছোট কয়টি মান, মাঝে মাঝে মান বদলায়” — প্রতিটি ব্লক সাজিয়ে রাখুন; পূর্ণ ব্লকে binary search (O(log B)), প্রান্তে সরাসরি গোনা; প্রশ্ন O((n/B) log B + B), আপডেট মানে একটি ব্লক আবার সাজানো। একইভাবে ব্লকের মধ্যে অন্য কোনো ছোট স্ট্রাকচার রাখা যায় — জোড়া লাগানোর নিয়ম না জানলেও চলে।
• মাঝারি n আর cache: ব্লকগুলো মেমরিতে পাশাপাশি, প্রান্তের হাঁটা ক্রমিক — আধুনিক CPU-তে এটি খুব দ্রুত, তাই n = 10⁵-এ পার্থক্য প্রায়ই তত্ত্বের চেয়ে কম।

Sqrt-এর ধারণা শুধু অ্যারের ব্লকে সীমিত নয়। প্রশ্নের ওপর sqrt: আপডেটগুলো একটি ছোট তালিকায় জমা রাখুন, প্রতিটি প্রশ্নে স্থির স্ট্রাকচারের উত্তরের সাথে তালিকার আপডেটগুলোর প্রভাব হাতে মিলিয়ে নিন, আর তালিকা √q-এর বেশি লম্বা হলে পুরো স্ট্রাকচার নতুন করে বানান। Heavy/light ভাগ: গ্রাফে √m-এর বেশি degree-র vertex অল্প (সর্বোচ্চ 2√m টি), তাই তাদের আলাদাভাবে সামলান — ত্রিভুজ গোনার মতো সমস্যায় এটি O(m√m) দেয়। মূল দর্শন একই: দুই ধরনের খরচকে √ সীমায় ভারসাম্যে আনা।

৭ · Mo’s algorithm — প্রশ্নগুলো সাজিয়ে নিলে

এবার একটি কঠিন প্রশ্ন: “a[l..r]-এ কয়টি আলাদা মান আছে?” — যেমন একটি মোবাইল ব্যাংকিং অ্যাপের লেনদেনের লগে “সকাল ৯টা থেকে দুপুর ২টা পর্যন্ত কতজন আলাদা গ্রাহক লেনদেন করেছেন?” এটি segment tree-তে সহজে জোড়া যায় না: বাঁ অর্ধেকে ৩টি আলাদা, ডান অর্ধেকে ৪টি — মোট কত? জানা নেই, কারণ দুই পাশে একই গ্রাহক থাকতে পারেন। Sparse table-ও নয় — অপারেশনটি idempotent নয়।

কিন্তু একটি জিনিস সহজ: একটি জানালা [L, R]-এর উত্তর জানা থাকলে, জানালা এক ঘর বাড়ানো বা কমানোর পর নতুন উত্তর O(1)-এ। একটি frequency array cnt[x] রাখুন: একটি মান যোগ হলে cnt[x] ০ থেকে ১ হলে আলাদা মান এক বাড়ে; সরালে ১ থেকে ০ হলে এক কমে। তাহলে প্রতিটি প্রশ্নে জানালার দুই প্রান্ত (L আর R pointer) টেনে নতুন রেঞ্জে নিয়ে যান। সমস্যা: প্রশ্নগুলো এলোমেলো ক্রমে এলে pointer প্রতিবার পুরো অ্যারে জুড়ে লাফায় — প্রতি প্রশ্নে O(n), মোট O(nq).

Mo’s algorithm ঠিক এটিই করে। সব q টি প্রশ্ন আগে পড়ে নিন — অর্থাৎ এটি একটি offline algorithm, যা প্রশ্নের উত্তর তাদের নিজের ক্রমে না দিয়ে সুবিধামতো ক্রমে দেয় (উল্টোটি online, যেখানে আগের উত্তর না দিলে পরের প্রশ্ন আসে না)। তারপর:

1. ব্লকের মাপ B ≈ √n নিন। প্রশ্ন (l, r)-এর চাবি = (⌊l / B⌋, r).
2. প্রশ্নগুলো এই চাবি অনুযায়ী সাজান: আগে l-এর ব্লক, একই ব্লকে r বাড়ার ক্রমে।
3. খালি জানালা (L = 0, R = −1) থেকে শুরু করে প্রতিটি প্রশ্নে আগে জানালা বাড়ান, তারপর কমান: R ডানে, L বাঁয়ে, R বাঁয়ে, L ডানে — প্রতিটি সরানোয় add বা remove.
4. উত্তর জমা রাখুন প্রশ্নের মূল index-এ, যাতে শেষে মূল ক্রমে ছাপা যায়।

কেন O((n + q)√n) — pointer কতটা হাঁটে

প্রতিটি add বা remove O(1) ধরে নিন; তাহলে মোট সময় = সাজানো O(q log q) + pointer-এর মোট সরানো। দুটি pointer আলাদা করে গুনুন, B = √n ধরে:

• R pointer: l-এর একই ব্লকের প্রশ্নগুলোতে r বাড়ার ক্রমে সাজানো, তাই সেই ব্লকের ভেতরে R শুধু ডানে যায় — মোট সর্বোচ্চ n ঘর। নতুন ব্লকে ঢোকার সময় R একবার বাঁয়ে ফিরতে পারে, সেটিও সর্বোচ্চ n. ব্লক আছে ⌈n/B⌉ টি, তাই মোট O(n · n/B) = O(n√n).
• L pointer: একই ব্লকের দুটি পরপর প্রশ্নের l দুটিই একই ব্লকে, তাই L সর্বোচ্চ B ঘর সরে — q টি প্রশ্নে O(qB). ব্লক বদলানোর সময় L সর্বোচ্চ 2B সরে (পরের ব্লকগুলো ক্রমে আসে বলে সব মিলে O(n)). মোট O(q√n + n).

যোগ করে O((n + q)√n), জায়গা O(n + q) (অ্যারে, cnt আর উত্তর)। আরও নিখুঁতভাবে খরচ O(n²/B + qB); B = n/√q নিলে O(n√q) — q যখন n-এর চেয়ে অনেক ছোট, তখন এটি ভালো। মনে রাখুন, add/remove যদি O(1) না হয়ে O(log n) হয় (যেমন একটি set-এ রাখতে হলে), মোট খরচও log n গুণ বাড়ে।

একটি জনপ্রিয় ছোট উন্নতি: বিজোড় নম্বরের ব্লকে r কমার ক্রমে সাজান। তাহলে এক ব্লক শেষ করে R পুরো অ্যারে পেরিয়ে বাঁয়ে ফেরার বদলে ফেরার পথেই পরের ব্লকের প্রশ্নগুলো ধরে — বাস্তবে প্রায়ই অনেকটা দ্রুত, যদিও Big-O একই।

পুরো কোড — Mo দিয়ে আলাদা মান গোনা, brute force-এর সাথে মিলিয়ে

প্রোগ্রামটি প্রথমে ওপরের উদাহরণ চালায়, তারপর ৪০০ উপাদানের একটি এলোমেলো অ্যারেতে (মান ০ থেকে ২৯) ৪০০টি এলোমেলো প্রশ্নের উত্তর প্রতিটি রেঞ্জের set-এর আকারের সাথে মেলায়। সাথে গোনে Mo-র pointer কত ঘর সরল, আর brute force মোট কত ঘর পড়ত।

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
pair<vector<int>, long long> mo_distinct(const vector<int>& a, const vector<pair<int, int>>& qs, int maxv) {
    int B = 1; while (B * B < (int)a.size()) ++B;       // B = ceil(sqrt(n))
    vector<int> order(qs.size()), cnt(maxv + 1, 0), ans(qs.size());
    for (int i = 0; i < (int)qs.size(); ++i) order[i] = i;
    sort(order.begin(), order.end(), [&](int x, int y) {      // key: (block of l, r, index)
        return tuple(qs[x].first / B, qs[x].second, x) < tuple(qs[y].first / B, qs[y].second, y); });
    int L = 0, R = -1, distinct = 0; long long moves = 0;
    auto add = [&](int i) { if (cnt[a[i]]++ == 0) ++distinct; };
    auto drop = [&](int i) { if (--cnt[a[i]] == 0) --distinct; };
    for (int i : order) {
        auto [l, r] = qs[i];
        moves += abs(l - L) + abs(r - R);
        while (R < r) add(++R);                         // grow right, grow left, then shrink
        while (L > l) add(--L);
        while (R > r) drop(R--);
        while (L < l) drop(L++);
        ans[i] = distinct;
    }
    return {ans, moves};
}
unsigned long long seed = 2024;
int rnd(int m) { seed = (seed * 1103515245 + 12345) % 2147483648ULL; return int(seed % m); }
int main() {
    auto [ans, moves] = mo_distinct({1, 2, 1, 3, 2, 2, 4, 1}, {{0, 4}, {1, 3}, {5, 6}, {2, 6}}, 4);
    printf("answers:"); for (int x : ans) printf(" %d", x); printf(" | pointer moves: %lld\n", moves);
    int n = 400; vector<int> b(n); vector<pair<int, int>> qs; for (int& x : b) x = rnd(30);
    for (int i = 0; i < 400; ++i) { int l = rnd(n), r = rnd(n); qs.push_back({min(l, r), max(l, r)}); }
    auto [ans2, moves2] = mo_distinct(b, qs, 29);
    int bad = 0; long long cells = 0;
    for (int i = 0; i < 400; ++i) {
        auto [l, r] = qs[i]; cells += r - l + 1;
        bad += ans2[i] != (int)set<int>(b.begin() + l, b.begin() + r + 1).size(); }
    printf("random queries: %d, mismatches: %d\nMo pointer moves: %lld, brute force cells: %lld\n",
           (int)qs.size(), bad, moves2, cells);
}

answers: 3 3 2 4 | pointer moves: 14
random queries: 400, mismatches: 0
Mo pointer moves: 9668, brute force cells: 53654

def mo_distinct(a, qs, maxv):                # offline: distinct values in a[l..r]
    B = 1
    while B * B < len(a):                    # B = ceil(sqrt(n))
        B += 1
    order = sorted(range(len(qs)), key=lambda i: (qs[i][0] // B, qs[i][1], i))
    cnt, ans = [0] * (maxv + 1), [0] * len(qs)
    L, R, distinct, moves = 0, -1, 0, 0
    for i in order:
        l, r = qs[i]
        moves += abs(l - L) + abs(r - R)
        while R < r:                         # grow right, grow left, then shrink
            R += 1; cnt[a[R]] += 1; distinct += cnt[a[R]] == 1
        while L > l:
            L -= 1; cnt[a[L]] += 1; distinct += cnt[a[L]] == 1
        while R > r:
            cnt[a[R]] -= 1; distinct -= cnt[a[R]] == 0; R -= 1
        while L < l:
            cnt[a[L]] -= 1; distinct -= cnt[a[L]] == 0; L += 1
        ans[i] = distinct
    return ans, moves

a = [1, 2, 1, 3, 2, 2, 4, 1]
qs = [(0, 4), (1, 3), (5, 6), (2, 6)]
ans, moves = mo_distinct(a, qs, 4)
print("answers:", *ans, "| pointer moves:", moves)

seed = 2024
def rnd(m):                                  # same LCG as the C++ version
    global seed
    seed = (seed * 1103515245 + 12345) % 2147483648
    return seed % m

n = 400
b = [rnd(30) for _ in range(n)]
qs = [tuple(sorted((rnd(n), rnd(n)))) for _ in range(400)]
ans, moves = mo_distinct(b, qs, 29)
bad = sum(ans[i] != len(set(b[l:r + 1])) for i, (l, r) in enumerate(qs))
cells = sum(r - l + 1 for l, r in qs)
print(f"random queries: {len(qs)}, mismatches: {bad}")
print(f"Mo pointer moves: {moves}, brute force cells: {cells}")

answers: 3 3 2 4 | pointer moves: 14
random queries: 400, mismatches: 0
Mo pointer moves: 9668, brute force cells: 53654

Mo কোথায় চলে, কোথায় চলে না

চলে যখন: (১) সব প্রশ্ন আগে জানা, (২) কোনো আপডেট নেই (বা নিচের “আরও গভীরে” রূপ), (৩) জানালায় এক ঘর যোগ আর বাদ দুটোই সস্তা। উদাহরণ: রেঞ্জে আলাদা মান, রেঞ্জে কোনো মানের সর্বোচ্চ পুনরাবৃত্তি (একটু কৌশলে), রেঞ্জে “সমান মানের জোড়া কয়টি” (যোগে cnt[x] জোড়া বাড়ে), রেঞ্জে কয়টি জোড়ার XOR ঠিক k. চলে না: online প্রশ্নে (যেমন প্রতিটি প্রশ্ন আগের উত্তর দিয়ে এনক্রিপ্ট করা — প্রতিযোগিতায় ঠিক Mo আটকাতে এই কৌশল ব্যবহার হয়), বা যেখানে remove কঠিন (যেমন সর্বোচ্চ মান — বাদ দিলে পরের সর্বোচ্চ কে, জানা নেই; তখন শুধু-যোগের “rollback Mo” রূপ লাগে)।

৮ · তুলনা — কোন রেঞ্জ-প্রশ্নে কোন স্ট্রাকচার

এই মডিউলের সব রেঞ্জ-স্ট্রাকচার একসাথে। n = অ্যারের আকার; “অপারেশন” কলামে লেখা কোন ধরনের হিসাব সেটি স্বাভাবিকভাবে সামলায়।

সিদ্ধান্তের একটি সহজ ক্রম: আপডেট আছে কি? না থাকলে আর অপারেশনের উল্টো থাকলে prefix sum; উল্টো না থাকলে কিন্তু idempotent হলে sparse table. আপডেট থাকলে segment tree (সবচেয়ে সাধারণ) বা Fenwick (যোগফলে ছোট আর দ্রুত)। অপারেশন জোড়া লাগে না কিন্তু জানালায় add/remove সহজ, আর সব প্রশ্ন আগে জানা → Mo. আর সময়ের চাপে বা অদ্ভুত শর্তে sqrt — প্রায় সবসময় একটি নিরাপদ বিকল্প।

৯ · AI-এর যুগে রেঞ্জ-প্রশ্ন — দ্রুত কোড, ধীর বাগ

“Sparse table লিখে দাও” বা “Mo’s algorithm দিয়ে distinct count” — AI সহকারী কয়েক সেকেন্ডে পরিষ্কার দেখতে কোড দেবে। কিন্তু এই কৌশলগুলোর বাগ প্রায় সবই সীমানায়: একটি “+ 1” বা “− 1”, inclusive আর exclusive রেঞ্জের গোলমাল, ভুল log. ছোট উদাহরণে প্রায়ই উত্তর ঠিক আসে, কারণ ভুল ব্লকটির min কাকতালীয়ভাবে একই হতে পারে। আর complexity-র প্রশ্নে AI কখনো কখনো sparse table-কে “আপডেটসহ O(1)” বা Mo-কে “online-এ চলে” বলে ফেলে।

এই পর্বের কোডে AI সাধারণত যেসব ভুল করে

রেঞ্জ-প্রশ্নের কোড যাচাইয়ের চেকলিস্ট

• রেঞ্জ inclusive না half-open — পুরো কোডে একটিই নিয়ম রেখেছি, আর ফাংশনের পাশে মন্তব্যে লিখেছি
• log বের করেছি পূর্ণসংখ্যার lg অ্যারে বা bit_width/bit_length দিয়ে, floating-point দিয়ে নয়
• Edge case চালিয়েছি: n = 1, l = r, পুরো অ্যারে, len ঠিক দুইয়ের ঘাত, শেষ ব্লক ছোট (n পূর্ণবর্গ নয়)
• হাজারো এলোমেলো প্রশ্নে উত্তর brute force-এর সাথে মিলিয়েছি (stress testing), ছোট n আর ছোট মানের পরিসর দিয়ে, যাতে পুনরাবৃত্তি বেশি হয়
• Mo-তে আগে বাড়িয়ে পরে কমিয়েছি, আর উত্তর মূল index-এ রেখেছি
• AI-এর complexity দাবি যাচাই করেছি: কোন অপারেশন idempotent, আপডেট আছে কি না, প্রশ্ন offline কি না — শর্তগুলো স্পষ্ট লেখা আছে কি না