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

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

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

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

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

با داشتن یک آرایه $a[0 \dots n-1]$، یک ساختمان داده پیاده‌سازی کنید که امکان یافتن مجموع عناصر $a[l \dots r]$ برای $l$ و $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]$، و مقادیر $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 \dots 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]$ را برای بلاکی که این عنصر به آن تعلق دارد ($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] = 0$ هستند). در طول هر عملیات "اضافه کردن"، باید $\delta$ را به $b[k]$ برای تمام بلاک‌هایی که به بازه $[l, r]$ تعلق دارند اضافه کنیم و $\delta$ را به $a[i]$ برای تمام عناصری که به "دنباله"‌های بازه تعلق دارند، اضافه کنیم. پاسخ به پرس‌وجوی $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})$ استفاده شود. این ممکن است بسیار بدتر از روش‌های بخش قبل به نظر برسد، زیرا پیچیدگی آن کمی بدتر از چیزی است که قبلاً داشتیم و نمی‌تواند مقادیر را بین دو پرس‌وجو به‌روزرسانی کند. اما در بسیاری از موقعیت‌ها این روش مزایایی دارد. در تجزیه جذر معمولی، ما باید پاسخ‌ها را برای هر بلاک پیش‌محاسبه کنیم و در هنگام پاسخ به پرس‌وجوها آنها را ادغام کنیم. در برخی مسائل، این مرحله ادغام می‌تواند کاملاً مشکل‌ساز باشد. برای مثال، وقتی هر پرس‌وجو می‌خواهد مد بازه خود (عددی که بیشترین تکرار را دارد) را پیدا کند. برای این کار، هر بلاک باید تعداد هر عدد در خود را در نوعی ساختمان داده ذخیره کند و دیگر نمی‌توانیم مرحله ادغام را به اندازه کافی سریع انجام دهیم. الگوریتم مو از یک رویکرد کاملاً متفاوت استفاده می‌کند که می‌تواند به این نوع پرس‌وجوها سریع پاسخ دهد، زیرا تنها یک ساختمان داده را نگهداری می‌کند و تنها عملیات با آن آسان و سریع هستند.

ایده این است که به پرس‌وجوها با ترتیب خاصی بر اساس اندیس‌ها پاسخ دهیم. ابتدا به تمام پرس‌وجوهایی که اندیس چپ آنها در بلاک 0 است پاسخ می‌دهیم، سپس به پرس‌وجوهایی که اندیس چپ آنها در بلاک 1 است و به همین ترتیب. و همچنین باید به پرس‌وجوهای یک بلاک با ترتیب خاصی پاسخ دهیم، یعنی مرتب شده بر اساس اندیس راست پرس‌وجوها.

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

از آنجایی که ما ترتیب پاسخ به پرس‌وجوها را تغییر می‌دهیم، این کار تنها زمانی ممکن است که مجاز به پاسخ به پرس‌وجوها به صورت آفلاین باشیم.

پیاده‌سازی

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

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

می‌توانید در مورد رویکرد مرتب‌سازی حتی سریع‌تر اینجا بخوانید.

مسائل تمرینی