স্কোয়ার্ট ডিকম্পোজিশন#

স্কোয়ার্ট ডিকম্পোজিশন হলো একটি পদ্ধতি (বা ডেটা স্ট্রাকচার) যা কিছু সাধারণ অপারেশন (সাব-অ্যারের উপাদানের যোগফল বের করা, সর্বনিম্ন/সর্বোচ্চ উপাদান বের করা, ইত্যাদি) $O(\sqrt n)$ অপারেশনে সম্পন্ন করতে দেয়, যা সরল অ্যালগরিদমের $O(n)$ থেকে অনেক দ্রুত।

প্রথমে আমরা এই ধারণার সবচেয়ে সরল প্রয়োগের জন্য ডেটা স্ট্রাকচার বর্ণনা করি, তারপর দেখাই কিভাবে এটিকে অন্য কিছু সমস্যা সমাধানের জন্য সাধারণীকরণ করা যায়, এবং শেষে এই ধারণার একটু ভিন্ন ব্যবহার দেখি: ইনপুট রিকোয়েস্টগুলোকে sqrt ব্লকে ভাগ করা।

স্কোয়ার্ট-ডিকম্পোজিশন ভিত্তিক ডেটা স্ট্রাকচার#

একটি অ্যারে $a[0 \dots n-1]$ দেওয়া আছে, এমন একটি ডেটা স্ট্রাকচার ইমপ্লিমেন্ট করুন যা যেচ্ছা $l$ এবং $r$ এর জন্য $a[l \dots r]$ উপাদানগুলোর যোগফল $O(\sqrt n)$ অপারেশনে বের করতে পারে।

বর্ণনা#

স্কোয়ার্ট ডিকম্পোজিশনের মূল ধারণা হলো প্রিপ্রসেসিং। আমরা অ্যারে $a$ কে প্রায় $\sqrt n$ দৈর্ঘ্যের ব্লকে ভাগ করবো, এবং প্রতিটি ব্লক $i$ এর জন্য এর উপাদানগুলোর যোগফল $b[i]$ আগে থেকে হিসাব করবো।

আমরা ধরে নিতে পারি যে ব্লকের আকার এবং ব্লকের সংখ্যা উভয়ই $\sqrt n$ এর ঊর্ধ্ব পূর্ণ সংখ্যার সমান:

$$ s = \lceil \sqrt n \rceil $$

তাহলে অ্যারে $a$ নিচের মতো করে ব্লকে ভাগ হয়:

$$ \underbrace{a[0], a[1], \dots, a[s-1]}_{\text{b[0]}}, \underbrace{a[s], \dots, a[2s-1]}_{\text{b[1]}}, \dots, \underbrace{a[(s-1) \cdot s], \dots, a[n-1]}_{\text{b[s-1]}} $$

শেষ ব্লকে অন্যগুলোর চেয়ে কম উপাদান থাকতে পারে (যদি $n$, $s$ এর গুণিতক না হয়), আলোচনার জন্য এটি গুরুত্বপূর্ণ নয় (কারণ এটি সহজেই সামলানো যায়)। সুতরাং, প্রতিটি ব্লক $k$ এর জন্য, আমরা এর উপাদানগুলোর যোগফল $b[k]$ জানি:

$$ b[k] = \sum\limits_{i=k\cdot s}^{\min {(n-1,(k+1)\cdot s - 1})} a[i] $$

তাহলে, আমরা $b[k]$ এর মানগুলো হিসাব করেছি (এতে $O(n)$ অপারেশন লেগেছে)। এগুলো কিভাবে প্রতিটি কোয়েরি $[l, r]$ এর উত্তর দিতে সাহায্য করতে পারে? লক্ষ্য করুন যে ইন্টারভ্যাল $[l, r]$ যথেষ্ট লম্বা হলে, এতে কয়েকটি সম্পূর্ণ ব্লক থাকবে, এবং সেই ব্লকগুলোর উপাদানের যোগফল একটি মাত্র অপারেশনে বের করা যাবে। ফলে, ইন্টারভ্যাল $[l, r]$ এ শুধুমাত্র দুটি ব্লকের অংশ থাকবে, এবং সেই অংশগুলোর উপাদানের যোগফল সরলভাবে হিসাব করতে হবে।

সুতরাং, $[l, r]$ ইন্টারভ্যালে উপাদানের যোগফল হিসাব করতে আমাদের শুধু দুটি “লেজ” এর উপাদানের যোগ করতে হবে: $[l\dots (k + 1)\cdot s-1]$ এবং $[p\cdot s\dots r]$, এবং $k + 1$ থেকে $p-1$ পর্যন্ত সব ব্লকের $b[i]$ মান যোগ করতে হবে:

$$ \sum\limits_{i=l}^r a[i] = \sum\limits_{i=l}^{(k+1) \cdot s-1} a[i] + \sum\limits_{i=k+1}^{p-1} b[i] + \sum\limits_{i=p\cdot s}^r a[i] $$

নোট: যখন $k = p$, অর্থাৎ $l$ এবং $r$ একই ব্লকে, সূত্রটি প্রয়োগ করা যাবে না, এবং যোগফল সরলভাবে হিসাব করতে হবে।

এই পদ্ধতি আমাদের অপারেশনের সংখ্যা উল্লেখযোগ্যভাবে কমাতে দেয়। প্রকৃতপক্ষে, প্রতিটি “লেজ” এর আকার ব্লকের দৈর্ঘ্য $s$ এর বেশি নয়, এবং যোগফলে ব্লকের সংখ্যা $s$ এর বেশি নয়। যেহেতু আমরা $s \approx \sqrt n$ বেছে নিয়েছি, $[l, r]$ ইন্টারভ্যালে উপাদানের যোগফল বের করতে প্রয়োজনীয় মোট অপারেশনের সংখ্যা $O(\sqrt n)$।

ইমপ্লিমেন্টেশন#

সবচেয়ে সরল ইমপ্লিমেন্টেশন দিয়ে শুরু করা যাক:

// input data
int n;
vector<int> a (n);

// preprocessing
int len = (int) sqrt (n + .0) + 1; // size of the block and the number of blocks
vector<int> b (len);
for (int i=0; i<n; ++i)
    b[i / len] += a[i];

// answering the queries
for (;;) {
    int l, r;
  // read input data for the next query
    int sum = 0;
    for (int i=l; i<=r; )
        if (i % len == 0 && i + len - 1 <= r) {
            // if the whole block starting at i belongs to [l, r]
            sum += b[i / len];
            i += len;
        }
        else {
            sum += a[i];
            ++i;
        }
}

এই ইমপ্লিমেন্টেশনে অযৌক্তিকভাবে অনেক ভাগ অপারেশন আছে (যা অন্যান্য পাটিগণিত অপারেশনের চেয়ে অনেক ধীর)। এর পরিবর্তে, আমরা $l$ এবং $r$ ইনডেক্স ধারণকারী ব্লকের ইনডেক্স $c_l$ এবং $c_r$ হিসাব করতে পারি, এবং $c_l$ ও $c_r$ ব্লকে “লেজ” এর আলাদা প্রসেসিং সহ $c_l+1 \dots c_r-1$ ব্লকগুলোর মধ্য দিয়ে লুপ করতে পারি। এই পদ্ধতি বর্ণনার শেষ সূত্রের সাথে মিলে যায়, এবং $c_l = c_r$ কেসটিকে বিশেষ কেস বানায়।

int sum = 0;
int c_l = l / len,   c_r = r / len;
if (c_l == c_r)
    for (int i=l; i<=r; ++i)
        sum += a[i];
else {
    for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)
        sum += a[i];
    for (int i=c_l+1; i<=c_r-1; ++i)
        sum += b[i];
    for (int i=c_r*len; i<=r; ++i)
        sum += a[i];
}

অন্যান্য সমস্যা#

এখন পর্যন্ত আমরা একটি ধারাবাহিক সাব-অ্যারের উপাদানের যোগফল বের করার সমস্যা নিয়ে আলোচনা করছিলাম। এই সমস্যাটি পৃথক অ্যারে উপাদান আপডেট করার অনুমতি দিতে সম্প্রসারিত করা যায়। যদি একটি উপাদান $a[i]$ পরিবর্তন হয়, তাহলে এই উপাদানটি যে ব্লকে আছে সেই $b[k]$ এর মান একটি অপারেশনে আপডেট করাই যথেষ্ট ($k = i / s$):

$$ b[k] += a_{new}[i] - a_{old}[i] $$

অন্যদিকে, উপাদানের যোগফল বের করার কাজটি একটি সাব-অ্যারের সর্বনিম্ন/সর্বোচ্চ উপাদান বের করার কাজ দিয়ে প্রতিস্থাপন করা যায়। যদি এই সমস্যায় পৃথক উপাদানের আপডেটও সামলাতে হয়, $b[k]$ এর মান আপডেট করাও সম্ভব, কিন্তু এজন্য $O(s) = O(\sqrt{n})$ অপারেশনে ব্লক $k$ এর সব মানের মধ্য দিয়ে ইটারেট করতে হবে।

স্কোয়ার্ট ডিকম্পোজিশন একইভাবে আরো অনেক শ্রেণীর সমস্যায় প্রয়োগ করা যায়: শূন্য উপাদানের সংখ্যা বের করা, প্রথম অ-শূন্য উপাদান খুঁজে বের করা, নির্দিষ্ট শর্ত পূরণ করে এমন উপাদান গণনা ইত্যাদি।

আরেকটি শ্রেণীর সমস্যা দেখা দেয় যখন আমাদের ইন্টারভ্যালে অ্যারে উপাদান আপডেট করতে হয়: বিদ্যমান উপাদানে যোগ করা বা একটি নির্দিষ্ট মান দিয়ে প্রতিস্থাপন করা।

উদাহরণস্বরূপ, ধরুন আমরা একটি অ্যারেতে দুই ধরনের অপারেশন করতে পারি: $[l, r]$ ইন্টারভ্যালের সব অ্যারে উপাদানে একটি নির্দিষ্ট মান $\delta$ যোগ করা অথবা $a[i]$ উপাদানের মান কোয়েরি করা। ধরি $b[k]$ এ ব্লক $k$ এর সব উপাদানে যে মান যোগ করতে হবে তা সংরক্ষণ করি (শুরুতে সব $b[k] = 0$)। প্রতিটি “যোগ” অপারেশনে $[l, r]$ ইন্টারভ্যালে থাকা সব ব্লকের জন্য $b[k]$ তে $\delta$ যোগ করতে হবে এবং ইন্টারভ্যালের “লেজ” এ থাকা সব উপাদানে $a[i]$ তে $\delta$ যোগ করতে হবে। কোয়েরি $i$ এর উত্তর হলো সহজভাবে $a[i] + b[i/s]$। এভাবে “যোগ” অপারেশনের কমপ্লেক্সিটি $O(\sqrt{n})$, এবং কোয়েরির উত্তরের কমপ্লেক্সিটি $O(1)$।

শেষত, এই দুই শ্রেণীর সমস্যা একত্রিত করা যায় যদি কাজে ইন্টারভ্যালে উপাদান আপডেট এবং ইন্টারভ্যালে কোয়েরি উভয়ই করতে হয়। উভয় অপারেশন $O(\sqrt{n})$ কমপ্লেক্সিটিতে করা যায়। এর জন্য দুটি ব্লক অ্যারে $b$ এবং $c$ প্রয়োজন: একটি উপাদান আপডেটের ট্র্যাক রাখতে এবং আরেকটি কোয়েরির উত্তরের ট্র্যাক রাখতে।

স্কোয়ার্ট ডিকম্পোজিশন ব্যবহার করে সমাধানযোগ্য আরো সমস্যা আছে, যেমন, সংখ্যার একটি সেট রক্ষণাবেক্ষণ করা যেখানে সংখ্যা যোগ/মুছে ফেলা, কোনো সংখ্যা সেটে আছে কিনা পরীক্ষা করা এবং $k$-তম বৃহত্তম সংখ্যা খুঁজে বের করা সম্ভব হবে। এটি সমাধান করতে সংখ্যাগুলো ক্রমবর্ধমান ক্রমে সংরক্ষণ করতে হবে, প্রতিটিতে $\sqrt{n}$ সংখ্যা সহ কয়েকটি ব্লকে ভাগ করে। প্রতিবার কোনো সংখ্যা যোগ/মুছে ফেলার সময়, পাশের ব্লকের শুরু ও শেষের মধ্যে সংখ্যা সরিয়ে ব্লকগুলো পুনঃসন্তুলিত করতে হবে।

Mo-এর অ্যালগরিদম#

একটি অনুরূপ ধারণা, স্কোয়ার্ট ডিকম্পোজিশনের উপর ভিত্তি করে, রেঞ্জ কোয়েরি ($Q$) অফলাইনে $O((N+Q)\sqrt{N})$ এ উত্তর দিতে ব্যবহার করা যায়। এটি পূর্ববর্তী বিভাগের পদ্ধতিগুলোর চেয়ে কিছুটা খারাপ মনে হতে পারে, কারণ এটি আগের চেয়ে সামান্য খারাপ কমপ্লেক্সিটি এবং দুটি কোয়েরির মধ্যে মান আপডেট করতে পারে না। কিন্তু অনেক পরিস্থিতিতে এই পদ্ধতির সুবিধা আছে। একটি সাধারণ স্কোয়ার্ট ডিকম্পোজিশনে, আমাদের প্রতিটি ব্লকের উত্তর আগে থেকে হিসাব করতে হয়, এবং কোয়েরির উত্তর দেওয়ার সময় সেগুলো মার্জ করতে হয়। কিছু সমস্যায় এই মার্জ ধাপটি বেশ সমস্যাজনক হতে পারে। যেমন যখন প্রতিটি কোয়েরি তার রেঞ্জের মোড (সবচেয়ে বেশিবার প্রদর্শিত সংখ্যা) জানতে চায়। এজন্য প্রতিটি ব্লকে কোনো ধরনের ডেটা স্ট্রাকচারে প্রতিটি সংখ্যার গণনা সংরক্ষণ করতে হবে, এবং আমরা আর যথেষ্ট দ্রুত মার্জ ধাপ সম্পাদন করতে পারব না। Mo-এর অ্যালগরিদম সম্পূর্ণ ভিন্ন একটি পদ্ধতি ব্যবহার করে, যা এই ধরনের কোয়েরি দ্রুত উত্তর দিতে পারে, কারণ এটি শুধুমাত্র একটি ডেটা স্ট্রাকচারের ট্র্যাক রাখে, এবং এর সাথে অপারেশনগুলো সহজ ও দ্রুত।

ধারণাটি হলো ইনডেক্সের উপর ভিত্তি করে একটি বিশেষ ক্রমে কোয়েরির উত্তর দেওয়া। আমরা প্রথমে সেই সব কোয়েরির উত্তর দেবো যাদের বাম ইনডেক্স ব্লক ০ তে, তারপর সেই সব কোয়েরির উত্তর দেবো যাদের বাম ইনডেক্স ব্লক ১ তে এবং এভাবে চলবে। এবং আমাদের একটি ব্লকের কোয়েরিগুলোও বিশেষ ক্রমে উত্তর দিতে হবে, যথা কোয়েরির ডান ইনডেক্স অনুসারে সাজানো।

ইতিমধ্যে বলা হয়েছে আমরা একটি একক ডেটা স্ট্রাকচার ব্যবহার করবো। এই ডেটা স্ট্রাকচার রেঞ্জ সম্পর্কে তথ্য সংরক্ষণ করবে। শুরুতে এই রেঞ্জ খালি থাকবে। যখন আমরা পরবর্তী কোয়েরির (বিশেষ ক্রমে) উত্তর দিতে চাই, আমরা সহজভাবে বর্তমান রেঞ্জের দুই পাশে উপাদান যোগ/সরিয়ে রেঞ্জ বাড়াই বা কমাই, যতক্ষণ না আমরা এটিকে কোয়েরি রেঞ্জে রূপান্তরিত করি। এভাবে, আমাদের একবারে শুধু একটি উপাদান যোগ বা সরাতে হয়, যা আমাদের ডেটা স্ট্রাকচারে বেশ সহজ অপারেশন হওয়া উচিত।

যেহেতু আমরা কোয়েরির উত্তর দেওয়ার ক্রম পরিবর্তন করি, এটি শুধুমাত্র তখনই সম্ভব যখন আমাদের কোয়েরি অফলাইন মোডে উত্তর দেওয়ার অনুমতি থাকে।

ইমপ্লিমেন্টেশন#

Mo-এর অ্যালগরিদমে আমরা দুটি ফাংশন ব্যবহার করি: একটি রেঞ্জে একটি ইনডেক্স যোগ করার জন্য এবং একটি রেঞ্জ থেকে একটি ইনডেক্স সরানোর জন্য যা আমরা বর্তমানে রক্ষণাবেক্ষণ করছি।

void remove(idx);  // TODO: remove value at idx from data structure
void add(idx);     // TODO: add value at idx from data structure
int get_answer();  // TODO: extract the current answer of the data structure

int block_size;

struct Query {
    int l, r, idx;
    bool operator<(Query other) const
    {
        return make_pair(l / block_size, r) <
               make_pair(other.l / block_size, other.r);
    }
};

vector<int> mo_s_algorithm(vector<Query> queries) {
    vector<int> answers(queries.size());
    sort(queries.begin(), queries.end());

    // TODO: initialize data structure

    int cur_l = 0;
    int cur_r = -1;
    // invariant: data structure will always reflect the range [cur_l, cur_r]
    for (Query q : queries) {
        while (cur_l > q.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < q.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < q.l) {
            remove(cur_l);
            cur_l++;
        }
        while (cur_r > q.r) {
            remove(cur_r);
            cur_r--;
        }
        answers[q.idx] = get_answer();
    }
    return answers;
}

সমস্যার উপর ভিত্তি করে আমরা ভিন্ন ডেটা স্ট্রাকচার ব্যবহার করতে পারি এবং সেই অনুযায়ী add/remove/get_answer ফাংশন পরিবর্তন করতে পারি। উদাহরণস্বরূপ যদি আমাদের রেঞ্জ যোগফল কোয়েরি করতে বলা হয় তাহলে আমরা ডেটা স্ট্রাকচার হিসেবে একটি সাধারণ ইন্টিজার ব্যবহার করি, যা শুরুতে $0$। add ফাংশন সহজভাবে পজিশনের মান যোগ করবে এবং পরবর্তীতে উত্তর ভেরিয়েবল আপডেট করবে। অন্যদিকে remove ফাংশন পজিশনের মান বিয়োগ করবে এবং পরবর্তীতে উত্তর ভেরিয়েবল আপডেট করবে। এবং get_answer শুধু ইন্টিজারটি রিটার্ন করে।

মোড-কোয়েরির উত্তর দিতে, আমরা বর্তমান রেঞ্জে প্রতিটি সংখ্যা কতবার দেখা যায় তা সংরক্ষণ করতে একটি বাইনারি সার্চ ট্রি (যেমন map<int, int>) এবং সংখ্যাগুলোর গণনা ক্রমে রাখতে একটি দ্বিতীয় বাইনারি সার্চ ট্রি (যেমন set<pair<int, int>>) ব্যবহার করতে পারি। add মেথড দ্বিতীয় BST থেকে বর্তমান সংখ্যা সরায়, প্রথমটিতে গণনা বাড়ায়, এবং সংখ্যাটি দ্বিতীয়টিতে আবার ঢোকায়। removeও একই কাজ করে, শুধু গণনা কমায়। এবং get_answer শুধু দ্বিতীয় ট্রি দেখে $O(1)$ এ সেরা মান রিটার্ন করে।

কমপ্লেক্সিটি#

সব কোয়েরি সাজাতে $O(Q \log Q)$ লাগবে।

অন্যান্য অপারেশনগুলোর কী হবে? add এবং remove কতবার কল হবে?

ধরি ব্লকের আকার $S$।

যদি আমরা শুধু একই ব্লকে বাম ইনডেক্স আছে এমন সব কোয়েরি দেখি, কোয়েরিগুলো ডান ইনডেক্স অনুসারে সাজানো। তাই এই সব কোয়েরি মিলিয়ে আমরা add(cur_r) এবং remove(cur_r) শুধু $O(N)$ বার কল করবো। এটি সব ব্লকের জন্য $O(\frac{N}{S} N)$ কল দেয়।

দুটি কোয়েরির মধ্যে cur_l এর মান সর্বোচ্চ $O(S)$ পরিবর্তন হতে পারে। তাই আমাদের add(cur_l) এবং remove(cur_l) এর অতিরিক্ত $O(S Q)$ কল আছে।

$S \approx \sqrt{N}$ হলে এটি মোট $O((N + Q) \sqrt{N})$ অপারেশন দেয়। সুতরাং কমপ্লেক্সিটি হলো $O((N+Q)F\sqrt{N})$ যেখানে $O(F)$ হলো add এবং remove ফাংশনের কমপ্লেক্সিটি।

রানটাইম উন্নতির টিপস#

ঠিক $\sqrt{N}$ ব্লক সাইজ সবসময় সেরা রানটাইম দেয় না। উদাহরণস্বরূপ, $\sqrt{N}=750$ হলে ব্লক সাইজ $700$ বা $800$ ভালো চলতে পারে। আরো গুরুত্বপূর্ণ, রানটাইমে ব্লক সাইজ হিসাব করবেন না - একে const বানান। ধ্রুবক দ্বারা ভাগ কম্পাইলার দ্বারা ভালোভাবে অপটিমাইজ হয়।
বিজোড় ব্লকে ডান ইনডেক্স ক্রমবর্ধমান ক্রমে এবং জোড় ব্লকে ক্রমহ্রাসমান ক্রমে সাজান। এটি ডান পয়েন্টারের চলাচল কমিয়ে দেবে, কারণ স্বাভাবিক সাজানো প্রতিটি ব্লকের শুরুতে ডান পয়েন্টারকে শেষ থেকে শুরুতে ফেরত নিয়ে যাবে। উন্নত সংস্করণে এই রিসেটিং আর প্রয়োজন নেই।

bool cmp(pair<int, int> p, pair<int, int> q) {
    if (p.first / BLOCK_SIZE != q.first / BLOCK_SIZE)
        return p < q;
    return (p.first / BLOCK_SIZE & 1) ? (p.second < q.second) : (p.second > q.second);
}

আরো দ্রুত সাজানোর পদ্ধতি সম্পর্কে এখানে পড়তে পারেন।

স্কোয়ার্ট ডিকম্পোজিশন#

স্কোয়ার্ট-ডিকম্পোজিশন ভিত্তিক ডেটা স্ট্রাকচার#

বর্ণনা#

ইমপ্লিমেন্টেশন#

অন্যান্য সমস্যা#

Mo-এর অ্যালগরিদম#

ইমপ্লিমেন্টেশন#

কমপ্লেক্সিটি#

রানটাইম উন্নতির টিপস#

অনুশীলন সমস্যা#