پرش به محتویات

تجزیه جذر (Sqrt Decomposition)

ببین، «تجزیه جذر» یا Sqrt Decomposition یه تکنیک (یا میشه گفت یه نوع ساختمان داده) خیلی باحاله که بهت اجازه میده یه سری کارهای پرتکرار (مثل پیدا کردن جمع یه تیکه از آرایه، یا پیدا کردن مینیمم/ماکزیمم و اینجور چیزا) رو توی $O(\sqrt n)$ انجام بدی. این سرعتش خیلی از راه حل ساده و دم‌دستی $O(n)$ بیشتره.

اول از همه، با یکی از ساده‌ترین کاربردهای این ایده شروع می‌کنیم و ساختمان داده‌ش رو توضیح میدیم. بعدش بهت نشون میدم چطوری میشه این روش رو برای حل مسئله‌های دیگه هم به کار برد. آخر سر هم یه نگاهی به یه کاربرد یه کم متفاوت‌تر از این ایده می‌ندازیم: اینکه چطوری میشه درخواست‌ها (queries) رو به بلاک‌های جذری تقسیم کرد.

ساختمان داده مبتنی بر تجزیه جذر

فرض کن یه آرایه $a[0 \dots n-1]$ داریم. می‌خوایم یه ساختمان داده درست کنیم که بتونه جمع عناصر توی یه بازه دلخواه $a[l \dots r]$ رو توی زمان $O(\sqrt n)$ برامون حساب کنه.

شرح

کلک اصلیِ تجزیه جذر، توی پیش‌پردازشه. ما میایم آرایه $a$ رو به یه سری بلاک با طول تقریباً $\sqrt n$ تقسیم می‌کنیم. بعد برای هر بلاک $i$، جمع کل عنصرهای توش رو حساب می‌کنیم و توی $b[i]$ ذخیره می‌کنیم.

می‌تونیم فرض کنیم که هم سایز هر بلاک و هم تعداد بلاک‌ها، $\sqrt n$ گرد شده به بالاست:

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

اونوقت آرایه $a$ اینجوری به بلاک‌ها تقسیم میشه:

$$ \underbrace{a, a, \dots, a[s-1]}_{\text{b}}, \underbrace{a[s], \dots, a[2s-1]}_{\text{b}}, \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]$ به اندازه کافی بزرگ باشه، حتماً یه سری بلاک کامل رو شامل میشه. برای این بلاک‌های کامل، ما میتونیم جمع‌شون رو یهویی و توی یه حرکت حساب کنیم (چون از قبل تو $b$ ذخیره کردیم). در نتیجه، بازه $[l, r]$ فقط شامل یه تیکه از دوتا بلاک (یکی اولی، یکی آخری) میشه که باید جمع عنصراشون رو دونه به دونه حساب کنیم.

پس برای حساب کردن جمع کل توی بازه $[l, r]$، کافیه عناصر دوتا تیکه "دم و سر" بازه رو جمع کنیم: یعنی تیکه اول از بازه $[l\dots (k + 1)\cdot s-1]$ و تیکه آخر از بازه $[p\cdot s\dots r]$. بعدش هم مقادیر $b[i]$ رو برای تمام بلاک‌های وسطی، یعنی از $k + 1$ تا $p-1$ با هم جمع کنیم:

$$ \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)$.

پیاده‌سازی

بریم سراغ ساده‌ترین پیاده‌سازیش:

// داده‌های ورودی
int n;
vector<int> a (n);

// پیش‌پردازش
int len = (int) sqrt (n + .0) + 1; // اندازه بلاک و تعداد بلاک‌ها
vector<int> b (len);
for (int i=0; i<n; ++i)
    b[i / len] += a[i];

// پاسخ به پرس‌وجوها
for (;;) {
    int l, r;
  // خواندن داده‌های ورودی برای پرس‌وجوی بعدی
    int sum = 0;
    for (int i=l; i<=r; )
        if (i % len == 0 && i + len - 1 <= r) {
            // اگر کل بلاکی که از i شروع می‌شود در بازه [l, r] قرار داشته باشد
            sum += b[i / len];
            i += len;
        }
        else {
            sum += a[i];
            ++i;
        }
}

این پیاده‌سازی یه عالمه عمل تقسیم داره (که خیلی کندتر از بقیه حساب‌کتاب‌هاست). به جای این کار، میتونیم شماره بلاک‌هایی که $l$ و $r$ توشون هستن رو حساب کنیم (مثلاً $c_l$ و $c_r$)، بعد روی بلاک‌های وسطی ($c_l+1$ تا $c_r-1$) یه حلقه بزنیم و اون تیکه‌های "دم و سر" توی بلاک‌های $c_l$ و $c_r$ رو جداگونه پردازش کنیم. این روش دقیقاً همون فرمول آخریه که گفتیم و باعث میشه حالت $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]$ مربوط به همون بلاکی که $a[i]$ توشه ($k = i / s$) رو توی یه حرکت آپدیت کنیم:

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

از اون طرف، میشه به جای جمع عناصر، مسئله رو برای پیدا کردن عنصر مینیمم/ماکزیمم توی یه بازه هم استفاده کرد. اگه تو این حالت هم بخوایم آپدیت‌های تکی رو هندل کنیم، آپدیت کردن مقدار $b[k]$ باز هم ممکنه، ولی این دفعه برای پیدا کردن مینیمم/ماکزیمم جدید باید کل عناصر بلاک $k$ رو یه دور از اول تا آخر ببینیم که هزینه‌ش میشه $O(s) = O(\sqrt{n})$.

تجزیه جذر رو میشه به همین شکل برای یه عالمه مسئله دیگه هم استفاده کرد: مثلاً پیدا کردن تعداد صفرهای یه بازه، پیدا کردن اولین عنصر غیرصفر، شمردن عناصری که یه شرط خاصی دارن و کلی چیز دیگه.

یه سری مسائل دیگه هم هستن که توشون باید عناصر آرایه رو توی یه بازه آپدیت کنیم: مثلاً به همشون یه مقداری اضافه کنیم یا مقدارشون رو با یه چیز جدید عوض کنیم.

برای مثال، فرض کن دو جور عملیات داریم: یکی اینکه یه مقدار $\delta$ رو به همه عناصر توی بازه $[l, r]$ اضافه کنیم، و یکی دیگه اینکه مقدار یه عنصر خاص $a[i]$ رو بپرسیم. بیاید برای هر بلاک $k$ یه متغیر $b[k]$ بذاریم که مقداری که باید به کل اون بلاک اضافه بشه رو توش نگه داریم (اولش همه $b[k]$ ها صفرن). حالا هر بار که یه عملیات «اضافه کردن» داریم، $\delta$ رو به $b[k]$ برای همه بلاک‌های وسطی بازه $[l, r]$ اضافه می‌کنیم و برای عناصر توی اون تیکه‌های "دم و سر" هم $\delta$ رو دونه دونه به خود $a[i]$ ها اضافه می‌کنیم. جواب دادن به کوئریِ مقدار $a[i]$ هم خیلی ساده میشه: $a[i] + b[i/s]$. اینطوری، عملیات «اضافه کردن» $O(\sqrt{n})$ و جواب دادن به کوئری $O(1)$ طول میکشه.

آخرش هم میشه این دوتا دسته مسئله رو با هم قاطی کرد. یعنی مسائلی که هم آپدیت روی بازه دارن و هم کوئری روی بازه. هر دوی این عملیات رو میشه با پیچیدگی $O(\sqrt{n})$ انجام داد. برای این کار به دوتا آرایه برای بلاک‌ها نیاز داریم، مثلاً $b$ و $c$: یکی برای دنبال کردن آپدیت‌ها و اون یکی برای نگه داشتن جواب کوئری‌ها.

باز هم مسئله‌های دیگه‌ای هستن که با تجزیه جذر حل میشن. مثلاً فرض کن یه مسئله داریم که باید یه مجموعه‌ای از عددها رو نگه داریم و بتونیم بهش عدد اضافه/حذف کنیم، چک کنیم یه عدد توش هست یا نه، و $k$-امین عدد بزرگتر رو پیدا کنیم. برای حل این، باید عددها رو مرتب‌شده نگه داریم و اون‌ها رو به چندتا بلاک $\sqrt{n}$ تایی تقسیم کنیم. هر بار که یه عدد اضافه یا حذف میشه، باید با جابجا کردن عددها بین اول و آخر بلاک‌های بغل‌دستی، بلاک‌ها رو دوباره بالانس کنیم.

الگوریتم مو (Mo's algorithm)

یه ایده شبیه به همین، که اونم بر پایه تجزیه جذره، برای جواب دادن به کوئری‌های بازه‌ای ($Q$) به صورت آفلاین (یعنی وقتی همه کوئری‌ها رو از اول داریم) توی زمان $O((N+Q)\sqrt{N})$ استفاده میشه. شاید در نگاه اول به نظر بیاد این روش از روش‌های قبلی خیلی بدتره، چون هم پیچیدگی‌ش یه کم بیشتره و هم نمیتونه بین کوئری‌ها مقادیر رو آپدیت کنه. ولی این روش تو خیلی از موارد یه سری مزیت‌ها داره. توی تجزیه جذر معمولی، ما باید جواب‌ها رو برای هر بلاک از قبل حساب می‌کردیم و بعد موقع جواب دادن به کوئری‌ها، اون‌ها رو با هم ترکیب (merge) می‌کردیم. توی بعضی مسئله‌ها، این مرحله ترکیب کردن خیلی دردسر داره. مثلاً فرض کن هر کوئری بخواد مد (mode) بازه‌ش رو پیدا کنه (یعنی عددی که از همه بیشتر تکرار شده). برای این کار، هر بلاک باید تعداد تکرار هر عدد رو توی یه ساختمان داده‌ای چیزی ذخیره کنه و دیگه نمیشه مرحله ترکیب کردن رو سریع انجام داد. الگوریتم مو از یه راه کاملاً متفاوت استفاده می‌کنه که میتونه به این جور کوئری‌ها سریع جواب بده، چون فقط یه دونه ساختمان داده نگه میداره و عملیات‌هایی که باهاش انجام میشه ساده و سریع هستن.

ایده‌ش اینه که به کوئری‌ها با یه ترتیب خاصی که به اندیس‌هاشون ربط داره جواب بدیم. اول به همه کوئری‌هایی که اندیس چپ‌شون تو بلاک ۰ هست جواب میدیم، بعد اونایی که اندیس چپ‌شون تو بلاک ۱ هست، و همین‌جوری تا آخر. تازه، کوئری‌های مربوط به هر بلاک رو هم باید با یه ترتیب خاصی جواب بدیم، یعنی اون‌ها رو بر اساس اندیس راست‌شون مرتب می‌کنیم.

همونطور که گفتم، از یه ساختمان داده واحد استفاده می‌کنیم. این ساختمان داده اطلاعات مربوط به یه بازه رو ذخیره می‌کنه. اولش این بازه خالیه. وقتی می‌خوایم به کوئری بعدی (با اون ترتیب خاص خودمون) جواب بدیم، خیلی راحت بازه فعلی‌مون رو با اضافه یا حذف کردن عنصر از دو طرفش، بزرگ و کوچیک می‌کنیم تا دقیقاً به بازه اون کوئری برسیم. اینطوری، هر بار فقط لازمه یه عنصر رو اضافه یا حذف کنیم، که باید کارهای خیلی ساده‌ای توی ساختمان داده ما باشن.

چون داریم ترتیب جواب دادن به کوئری‌ها رو عوض می‌کنیم، این روش فقط وقتی جواب میده که اجازه داشته باشیم به کوئری‌ها به صورت آفلاین (offline) جواب بدیم (یعنی همه رو از اول داشته باشیم).

پیاده‌سازی

توی الگوریتم مو، ما از دوتا تابع استفاده می‌کنیم: یکی برای اضافه کردن یه اندیس به بازه‌ای که الان داریم، و یکی برای حذف کردنش.

void remove(idx);  // TODO: مقدار در اندیس idx را از ساختمان داده حذف کن
void add(idx);     // TODO: مقدار در اندیس idx را به ساختمان داده اضافه کن
int get_answer();  // TODO: پاسخ فعلی را از ساختمان داده استخراج کن

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: ساختمان داده را مقداردهی اولیه کن

    int cur_l = 0;
    int cur_r = -1;
    // ناوردا: ساختمان داده همیشه بازه [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 میاد عدد فعلی رو از درخت دوم حذف میکنه، تعدادش رو توی درخت اولی زیاد می‌کنه، و دوباره عدد رو با تعداد جدیدش توی درخت دوم وارد می‌کنه. 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)$ تغییر می‌کنه. پس ما $O(S Q)$ تا فراخوانی اضافه برای add(cur_l) و remove(cur_l) داریم.

اگه $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 براش بذار. کامپایلرها تقسیم بر عددهای ثابت رو خیلی خوب بهینه می‌کنن.
  • توی بلاک‌های با شماره فرد، کوئری‌ها رو بر اساس اندیس راست‌شون صعودی مرتب کن و توی بلاک‌های زوج، نزولی. این کلک باعث میشه حرکت اون اشاره‌گر راست cur_r کمتر بشه، چون توی مرتب‌سازی معمولی، اول هر بلاک، اشاره‌گر راست مجبوره از ته آرایه برگرده اول. با این نسخه بهینه‌تر، دیگه لازم نیست این اتفاق بیفته.
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);
}

اگه دوست داری در مورد یه روش مرتب‌سازی حتی سریع‌تر بخونی، یه نگاه به این لینک بنداز.

مسائل تمرینی