Сийрэг хүснэгт¶

Сийрэг хүснэгт гэдэг нь интервалын асуулгад хариулах боломж олгодог өгөгдлийн бүтэц юм. Энэ нь ихэнх интервалын асуулгад $O(\log n)$-д хариулж чадах боловч түүний жинхэнэ хүч нь интервалын минимум асуулгад (эсвэл эквивалент интервалын максимум асуулгад) хариулахад оршино. Тэдгээр асуулгын хувьд энэ нь хариуг $O(1)$ хугацаанд тооцоолж чадна.

Энэ өгөгдлийн бүтцийн цорын ганц сул тал нь зөвхөн өөрчлөгдөшгүй массив дээр ашиглаж болдогт оршино. Энэ нь массивыг хоёр асуулгын хооронд өөрчлөх боломжгүй гэсэн үг. Хэрэв массив дахь ямар нэг элемент өөрчлөгдвөл бүхэл өгөгдлийн бүтцийг дахин тооцоолох ёстой.

Зөн совин¶

Дурын сөрөг биш тоог хоёрын буурах зэргүүдийн нийлбэр хэлбэрээр цор ганцаар илэрхийлж болно. Энэ бол зүгээр л тооны хоёртын дүрслэлийн нэг хувилбар юм. Жишээ нь $13 = (1101)_2 = 8 + 4 + 1$. $x$ тооны хувьд хамгийн ихдээ $\lceil \log_2 x \rceil$ нэмэгдэхүүн байж болно.

Ижил үндэслэлээр дурын интервалыг урт нь хоёрын буурах зэрэг байх интервалуудын нэгдэл хэлбэрээр цор ганцаар илэрхийлж болно. Жишээ нь $[2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]$, энд бүхэл интервал 13 урттай, тус тусын интервалууд харгалзан 8, 4, 1 урттай. Мөн энд нэгдэл хамгийн ихдээ $\lceil \log_2(\text{интервалын урт}) \rceil$ интервалаас тогтоно.

Сийрэг хүснэгтийн гол санаа нь хоёрын зэрэг урттай интервалын асуулгуудын бүх хариуг урьдчилан тооцоолох явдал юм. Дараа нь өөр интервалын асуулгад интервалыг хоёрын зэрэг урттай интервалуудад хувааж, урьдчилан тооцоолсон хариуг хайж, тэдгээрийг нэгтгэн бүхэл хариу авах замаар хариулж болно.

Урьдчилсан тооцоолол¶

Бид урьдчилан тооцоолсон асуулгуудын хариуг хадгалахад 2 хэмжээст массив ашиглана. $\text{st}[i][j]$ нь $2^i$ урттай $[j, j + 2^i - 1]$ интервалын хариуг хадгална. 2 хэмжээст массивын хэмжээ нь $(K + 1) \times \text{MAXN}$ байх бөгөөд энд $\text{MAXN}$ нь боломжит хамгийн том массивын урт юм. $\text{K}$ нь $\text{K} \ge \lfloor \log_2 \text{MAXN} \rfloor$-г хангах ёстой, учир нь $2^{\lfloor \log_2 \text{MAXN} \rfloor}$ нь бидний дэмжих ёстой хоёрын зэрэг хамгийн том интервал юм. Боломжийн урттай массивын хувьд ($\le 10^7$ элемент), $K = 25$ сайн утга юм.

$\text{MAXN}$ хэмжээс нь (кэшэд ээлтэй) дараалсан санах ойн хандалтыг зөвшөөрөхийн тулд хоёрдугаарт байрлана.

int st[K + 1][MAXN];

$2^i$ урттай $[j, j + 2^i - 1]$ интервал нь хоёулаа $2^{i - 1}$ урттай $[j, j + 2^{i - 1} - 1]$ ба $[j + 2^{i - 1}, j + 2^i - 1]$ интервалуудад сайхан хуваагддаг тул бид динамик программчлал ашиглан хүснэгтийг үр ашигтайгаар үүсгэж болно:

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

$f$ функц нь асуулгын төрлөөс хамаарна. Интервалын нийлбэр асуулгын хувьд энэ нь нийлбэрийг, интервалын минимум асуулгын хувьд минимумыг тооцоолно.

Урьдчилсан тооцооллын time complexity нь $O(\text{N} \log \text{N})$.

Интервалын нийлбэр асуулга¶

Энэ төрлийн асуулгын хувьд бид интервал дахь бүх утгын нийлбэрийг олохыг хүсэж байна. Тиймээс $f$ функцийн байгалийн тодорхойлолт нь $f(x, y) = x + y$. Бид өгөгдлийн бүтцийг дараахаар байгуулж болно:

long long st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = st[i - 1][j] + st[i - 1][j + (1 << (i - 1))];

$[L, R]$ интервалын нийлбэр асуулгад хариулахын тулд бид хамгийн томоос эхлэн хоёрын бүх зэргээр давтана. Хоёрын зэрэг $2^i$ нь интервалын урт ($= R - L + 1$)-аас бага буюу тэнцүү болмогц бид интервалын эхний хэсэг $[L, L + 2^i - 1]$-г боловсруулж, үлдсэн интервал $[L + 2^i, R]$-ээр үргэлжлүүлнэ.

long long sum = 0;
for (int i = K; i >= 0; i--) {
    if ((1 << i) <= R - L + 1) {
        sum += st[i][L];
        L += 1 << i;
    }
}

Интервалын нийлбэр асуулгын time complexity нь $O(K) = O(\log \text{MAXN})$.

Интервалын минимум асуулга (RMQ)¶

Эдгээр нь Сийрэг хүснэгт гялалздаг асуулгууд юм. Интервалын минимумыг тооцоолохдоо бид интервал дахь утгыг нэг эсвэл хоёр удаа боловсруулах нь хамаагүй. Тиймээс интервалыг олон интервалд хуваахын оронд бид интервалыг хоёрын зэрэг урттай зөвхөн хоёр давхцах интервалд ч хувааж болно. Жишээ нь бид $[1, 6]$ интервалыг $[1, 4]$ ба $[3, 6]$ интервалуудад хувааж болно. $[1, 6]$-ийн интервалын минимум нь $[1, 4]$-ийн интервалын минимум ба $[3, 6]$-ийн интервалын минимумын минимумтай ижил нь тодорхой. Тиймээс бид $[L, R]$ интервалын минимумыг дараахаар тооцоолж болно:

$$\min(\text{st}[i][L], \text{st}[i][R - 2^i + 1]) \quad \text{ энд } i = \log_2(R - L + 1)$$

Энэ нь бид $\log_2(R - L + 1)$-г хурдан тооцоолж чадахыг шаардана. Үүнийг та бүх логарифмыг урьдчилан тооцоолох замаар хийж болно:

int lg[MAXN+1];
lg[1] = 0;
for (int i = 2; i <= MAXN; i++)
    lg[i] = lg[i/2] + 1;

Эсвэл log-г тогтмол орон зай, хугацаанд явцын дунд тооцоолж болно:

// C++20
#include <bit>
int log2_floor(unsigned long i) {
    return std::bit_width(i) - 1;
}

// pre C++20
int log2_floor(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

Энэ жишиг сорил нь lg массив ашиглах нь кэш алдалтаас болж илүү удаан болохыг харуулж байна.

Дараа нь бид Сийрэг хүснэгтийн бүтцийг урьдчилан тооцоолох хэрэгтэй. Энэ удаад бид $f$-г $f(x, y) = \min(x, y)$-ээр тодорхойлно.

int st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

$[L, R]$ интервалын минимумыг дараахаар тооцоолж болно:

int i = lg[R - L + 1];
int minimum = min(st[i][L], st[i][R - (1 << i) + 1]);

Интервалын минимум асуулгын time complexity нь $O(1)$.

Илүү олон төрлийн асуулгыг дэмждэг ижил төстэй өгөгдлийн бүтэц¶

Өмнөх хэсэгт авч үзсэн $O(1)$ аргын гол сул талуудын нэг нь энэ арга зөвхөн идемпотент функц-ийн асуулгыг дэмждэгт оршино. Өөрөөр хэлбэл интервалын минимум асуулгад маш сайн ажилладаг боловч энэ аргаар интервалын нийлбэр асуулгад хариулах боломжгүй.

Дурын төрлийн associative функцийг зохицуулж, интервалын асуулгад $O(1)$-д хариулж чадах ижил төстэй өгөгдлийн бүтэц бий. Тэдгээрийн нэгийг Огтлолцолгүй сийрэг хүснэгт гэж нэрлэдэг. Өөр нэг нь Квадрат язгуурын мод байх болно.