Квадрат язгуурын задаргаа¶

Квадрат язгуурын задаргаа гэдэг нь зарим түгээмэл үйлдлийг (дэд хэрчмийн элементүүдийн нийлбэрийг олох, хамгийн бага/их элементийг олох гэх мэт) $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)$ болно.

Implementation¶

Let's start with the simplest implementation:

// 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;
        }
}

This implementation has unreasonably many division operations (which are much slower than other arithmetical operations). Instead, we can calculate the indices of the blocks $c_l$ and $c_r$ which contain indices $l$ and $r$, and loop through blocks $c_l+1 \dots c_r-1$ with separate processing of the "tails" in blocks $c_l$ and $c_r$. This approach corresponds to the last formula in the description, and makes the case $c_l = c_r$ a special case.

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]$ өөрчлөгдвөл энэ элемент харьяалагдах блокийн ($k = i / s$) $b[k]$ утгыг нэг үйлдлээр шинэчлэхэд хангалттай:

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

Нөгөө талаас элементүүдийн нийлбэрийг олох даалгаврыг дэд хэрчмийн хамгийн бага/их элементийг олох даалгавраар сольж болно. Хэрэв энэ бодлого тус тусын элементийн шинэчлэлтийг мөн зохицуулах ёстой бол $b[k]$ утгыг шинэчлэх нь мөн боломжтой боловч блок $k$-ийн бүх утгаар $O(s) = O(\sqrt{n})$ үйлдлээр давтахыг шаардана.

Квадрат язгуурын задаргааг ижил төстэй байдлаар бусад бодлогуудын бүхэл ангид хэрэглэж болно: тэг элементийн тоог олох, эхний тэг биш элементийг олох, тодорхой шинжийг хангах элементүүдийг тоолох гэх мэт.

Бид массивын элементүүдийг интервал дээр шинэчлэх хэрэгтэй болоход өөр ангийн бодлого гарч ирнэ: одоо байгаа элементүүдийг нэмэгдүүлэх эсвэл өгөгдсөн утгаар солих.

Жишээ нь бид массив дээр хоёр төрлийн үйлдэл хийж болно гэж бодъё: $[l, r]$ интервал дээрх бүх массивын элементэд өгөгдсөн утга $\delta$ нэмэх, эсвэл элемент $a[i]$-ийн утгыг асуух. Блок $k$-ийн бүх элементэд нэмэх ёстой утгыг $b[k]$-д хадгалъя (эхэндээ бүх $b[k] = 0$). "Нэмэх" үйлдэл бүрд бид $[l, r]$ интервалд харьяалагдах бүх блокийн $b[k]$-д $\delta$ нэмж, интервалын "сүүл"-д харьяалагдах бүх элементийн $a[i]$-д $\delta$ нэмэх хэрэгтэй. $i$ асуулгын хариу нь зүгээр л $a[i] + b[i/s]$. Ингэснээр "нэмэх" үйлдэл $O(\sqrt{n})$ complexity-тэй, асуулгад хариулах нь $O(1)$ complexity-тэй болно.

Эцэст нь даалгавар нь интервал дээр элемент шинэчлэх ба интервал дээр асуулга хийх хоёуланг шаардвал эдгээр хоёр ангийн бодлогыг нэгтгэж болно. Хоёр үйлдлийг хоёуланг $O(\sqrt{n})$ complexity-тэйгээр хийж болно. Үүнд $b$ ба $c$ гэсэн хоёр блок массив шаардлагатай: нэг нь элементийн шинэчлэлтийг хянах, нөгөө нь асуулгын хариуг хянах.

Квадрат язгуурын задаргаа ашиглан бодож болох бусад бодлого бий, жишээ нь тоо нэмэх/устгах, тоо олонлогт харьяалагдах эсэхийг шалгах, $k$-р хамгийн их тоог олох боломжтой тооны олонлогийг хадгалах тухай бодлого. Үүнийг бодохын тулд тоонуудыг өсөх дарааллаар хадгалж, тус бүрд $\sqrt{n}$ тоотой хэд хэдэн блокт хуваах хэрэгтэй. Тоо нэмэх/устгах бүрд зэргэлдээ блокуудын эхлэл ба төгсгөлийн хооронд тоонуудыг зөөж блокуудыг дахин тэнцвэржүүлэх ёстой.

Мо-гийн алгоритм¶

Квадрат язгуурын задаргаанд суурилсан ижил төстэй санааг ашиглан интервалын асуулгууд ($Q$)-д офлайнаар $O((N+Q)\sqrt{N})$-д хариулж болно. Энэ нь өмнөх хэсгийн аргуудаас хамаагүй муу мэт сонсогдож болох, учир нь энэ нь бидний өмнө байсанаас арай муу complexity-тэй бөгөөд хоёр асуулгын хооронд утгыг шинэчилж чадахгүй. Гэвч олон нөхцөл байдалд энэ арга давуу талтай. Ердийн квадрат язгуурын задаргааны үед бид блок бүрийн хариуг урьдчилан тооцоолж, асуулгад хариулахдаа тэдгээрийг нэгтгэх ёстой. Зарим бодлогод энэ нэгтгэх алхам нэлээд асуудалтай байж болно. Жишээ нь асуулга бүр өөрийн интервалын хамгийн олон давтагдах утга (mode)-г олохыг асуух үед. Үүний тулд блок бүр өөр доторх тоо бүрийн тоог ямар нэг өгөгдлийн бүтцэд хадгалах ёстой болох ба бид нэгтгэх алхмыг цаашид хангалттай хурдан гүйцэтгэж чадахгүй болно. Мо-гийн алгоритм нь огт өөр аргыг ашигладаг бөгөөд ийм төрлийн асуулгад хурдан хариулж чадна, учир нь энэ нь зөвхөн нэг өгөгдлийн бүтцийг хянадаг ба түүнтэй хийх цорын ганц үйлдэл нь хялбар бөгөөд хурдан юм.

Санаа нь асуулгуудад индекс дээр үндэслэсэн тусгай дарааллаар хариулах явдал юм. Бид эхлээд зүүн индекс нь блок 0-д байх бүх асуулгад хариулж, дараа нь зүүн индекс нь блок 1-д байх бүх асуулгад хариулах гэх мэтчилэн. Мөн бид блокийн асуулгуудад тусгай дарааллаар буюу асуулгуудын баруун индексээр эрэмбэлэн хариулах ёстой.

Аль хэдийн хэлсэнчлэн бид ганц өгөгдлийн бүтэц ашиглана. Энэ өгөгдлийн бүтэц интервалын талаарх мэдээллийг хадгална. Эхэндээ энэ интервал хоосон байна. Бид дараагийн асуулгад (тусгай дарааллаар) хариулахыг хүсэх үед бид одоогийн интервалын хоёр талд элемент нэмэх/устгах замаар интервалыг зүгээр л өргөтгөх буюу багасгаж, түүнийг асуулгын интервал болгон хувиргана. Ингэснээр бид нэг зэрэг зөвхөн ганц элемент нэмэх буюу устгах хэрэгтэй болох ба энэ нь манай өгөгдлийн бүтцэд нэлээд хялбар үйлдлүүд байх ёстой.

Бид асуулгад хариулах дарааллыг өөрчилдөг тул энэ нь зөвхөн асуулгад офлайн горимд хариулахыг зөвшөөрсөн үед л боломжтой.

Implementation¶

In Mo's algorithm we use two functions for adding an index and for removing an index from the range which we are currently maintaining.

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;
}

Based on the problem we can use a different data structure and modify the add/remove/get_answer functions accordingly. For example if we are asked to find range sum queries then we use a simple integer as data structure, which is $0$ at the beginning. The add function will simply add the value of the position and subsequently update the answer variable. On the other hand remove function will subtract the value at position and subsequently update the answer variable. And get_answer just returns the integer.

For answering mode-queries, we can use a binary search tree (e.g. map<int, int>) for storing how often each number appears in the current range, and a second binary search tree (e.g. set<pair<int, int>>) for keeping counts of the numbers (e.g. as count-number pairs) in order. The add method removes the current number from the second BST, increases the count in the first one, and inserts the number back into the second one. remove does the same thing, it only decreases the count. And get_answer just looks at second tree and returns the best value in $O(1)$.

Complexity¶

Бүх асуулгыг эрэмбэлэхэд $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})$ үйлдэл өгнө. Тиймээс complexity нь $O((N+Q)F\sqrt{N})$ бөгөөд энд $O(F)$ нь add ба remove функцийн complexity юм.

Ажиллах хугацааг сайжруулах зөвлөмж¶

Яг $\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);
}

Бүр илүү хурдан эрэмбэлэх аргын талаар эндээс уншиж болно.

Квадрат язгуурын задаргаа¶