Агуулгыг алгасах

Хамгийн бага нийтлэг өвөг - Фарах-Колтон ба Бендерийн алгоритм

$G$ нь мод байг. $(u, v)$ хэлбэрийн асуулга бүрийн хувьд бид зангилаа $u$ ба $v$-ийн хамгийн бага нийтлэг өвгийг олохыг хүсэж байна, өөрөөр хэлбэл $u$-ээс үндэс зангилаа хүрэх зам дээр орших, мөн $v$-ээс үндэс зангилаа хүрэх зам дээр орших зангилаа $w$-г олохыг хүсэж байгаа бөгөөд хэрэв ийм зангилаа олон байвал бид үндэс зангилаанаас хамгийн хол байгааг нь сонгоно. Өөрөөр хэлбэл хайж буй зангилаа $w$ нь $u$ ба $v$-ийн хамгийн бага өвөг юм. Тухайлбал хэрэв $u$ нь $v$-ийн өвөг бол $u$ нь тэдний хамгийн бага нийтлэг өвөг байна.

Энэ өгүүлэлд тайлбарлах алгоритмыг Фарах-Колтон ба Бендер нар боловсруулсан. Энэ нь асимптотоор оновчтой.

Алгоритм

Бид LCA бодлогыг RMQ бодлого болгон хураах сонгодог хураалтыг ашиглана. Бид DFS-ээр модны бүх зангилааг тойрч, зочилсон бүх зангилаа ба тэдгээр зангилааны өндрийг агуулсан массив хөтөлнө. Хоёр зангилаа $u$ ба $v$-ийн LCA нь тойролт дахь $u$ ба $v$-ийн орцуудын хооронд байрлах хамгийн бага өндөртэй зангилаа юм.

Дараах зурагт графын боломжит Эйлерийн тойролтыг, доорх жагсаалтад зочилсон зангилаанууд ба тэдгээрийн өндрийг харж болно.

LCA Эйлерийн тойролт
$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Nodes:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\ \hline \text{Heights:} & 1 & 2 & 3 & 2 & 3 & 2 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ \hline \end{array}$$

Энэ хураалтын талаар Хамгийн бага нийтлэг өвөг өгүүллээс дэлгэрэнгүй уншиж болно. Тэр өгүүлэлд интервалын минимумыг $O(\sqrt{N})$-д sqrt-задаргаагаар эсвэл Хэрчмийн мод ашиглан $O(\log N)$-д олсон. Энэ өгүүлэлд бид урьдчилсан боловсруулалтад ердөө $O(N)$ хугацаа зарцуулсаар байхын зэрэгцээ өгөгдсөн интервал дахь хамгийн бага элементийн асуулгыг $O(1)$ хугацаанд хэрхэн бодож болохыг үзнэ.

Хураагдсан RMQ бодлого маш өвөрмөц болохыг анзаар: массив дахь дурын хоёр зэргэлдээ элемент яг нэгээр ялгаатай (учир нь массивын элементүүд нь тойролтын дарааллаар зочилсон зангилаануудын өндрөөс өөр юу ч биш бөгөөд бид эсвэл удам руу очно, энэ тохиолдолд дараагийн элемент нэгээр их байна, эсвэл өвөг рүү буцна, энэ тохиолдолд дараагийн элемент нэгээр бага байна). Фарах-Колтон ба Бендерийн алгоритм яг энэ тусгайлсан RMQ бодлогын шийдийг тайлбарладаг.

Интервал дахь хамгийн бага элементийн асуулгыг гүйцэтгэхийг хүсэж буй массивыг $A$ гэж тэмдэглэе. $N$ нь $A$-ийн хэмжээ байна.

RMQ бодлогыг $O(N \log N)$ урьдчилсан боловсруулалт, асуулга бүрд $O(1)$-ээр бодоход ашиглаж болох энгийн өгөгдлийн бүтэц бий: Сийрэг хүснэгт. Бид элемент $T[i][j]$ бүр нь $[i, i + 2^j - 1]$ интервал дахь $A$-ийн минимумтай тэнцүү байх хүснэгт $T$ үүсгэнэ. $0 \leq j \leq \lceil \log N \rceil$ байх нь илэрхий тул Сийрэг хүснэгтийн хэмжээ $O(N \log N)$ байна. $T[i][j] = \min(T[i][j-1], T[i+2^{j-1}][j-1])$ болохыг анзаарснаар хүснэгтийг $O(N \log N)$-д амархан байгуулж болно.

Энэ өгөгдлийн бүтцийг ашиглан бид RMQ асуулгад $O(1)$-д хэрхэн хариулах вэ? Хүлээн авсан асуулга $[l, r]$ байг, тэгвэл хариу нь $\min(T[l][\text{sz}], T[r-2^{\text{sz}}+1][\text{sz}])$ бөгөөд энд $\text{sz}$ нь $2^{\text{sz}}$ нь интервалын урт $r-l+1$-ээс их биш байх хамгийн том зэрэг илтгэгч юм. Үнэндээ бид $[l, r]$ интервалыг аваад түүнийг $2^{\text{sz}}$ урттай хоёр хэрчмээр бүрхэж болно — нэг нь $l$-д эхэлж, нөгөө нь $r$-д төгсөнө. Эдгээр хэрчим давхцах боловч энэ нь бидний тооцоололд саад болохгүй. Асуулга бүрд $O(1)$ time complexity-д үнэхээр хүрэхийн тулд бид $1$-ээс $N$ хүртэлх боломжит бүх уртын хувьд $\text{sz}$-ийн утгыг мэдэх хэрэгтэй. Гэвч үүнийг амархан урьдчилан тооцоолж болно.

Одоо бид урьдчилсан боловсруулалтын complexity-г $O(N)$ хүртэл сайжруулахыг хүсэж байна.

Бид массив $A$-г $K = 0.5 \log N$ хэмжээтэй блокуудад хуваана, энд $\log$ нь 2 суурьтай логарифм юм. Блок бүрийн хувьд бид хамгийн бага элементийг тооцоолж, тэдгээрийг массив $B$-д хадгална. $B$ нь $\frac{N}{K}$ хэмжээтэй. Бид массив $B$-ээс сийрэг хүснэгт байгуулна. Түүний хэмжээ ба time complexity нь:

$$\frac{N}{K}\log\left(\frac{N}{K}\right) = \frac{2N}{\log(N)} \log\left(\frac{2N}{\log(N)}\right) =$$
$$= \frac{2N}{\log(N)} \left(1 + \log\left(\frac{N}{\log(N)}\right)\right) \leq \frac{2N}{\log(N)} + 2N = O(N)$$

Одоо бид зөвхөн блок бүрийн дотор интервал дахь хамгийн бага элементийн асуулгад хэрхэн хурдан хариулахыг сурах л үлдлээ. Үнэндээ хэрэв хүлээн авсан интервал дахь хамгийн бага элементийн асуулга $[l, r]$ байх ба $l$ ба $r$ өөр өөр блокт байвал хариу нь дараах гурван утгын хамгийн бага нь юм: $l$-ээс эхлэх $l$-ийн блокийн дагаврын минимум, $r$-д төгсөх $r$-ийн блокийн угтварын минимум, мөн тэдгээрийн хоорондох блокуудын минимум. Хоорондох блокуудын минимумд Сийрэг хүснэгт ашиглан $O(1)$-д хариулж болно. Тэгэхээр энэ нь бидэнд зөвхөн блокуудын доторх интервал дахь хамгийн бага элементийн асуулгыг үлдээж байна.

Энд бид массивын шинж чанарыг ашиглана. Массив дахь утгууд — эдгээр нь ердөө модны өндрийн утгууд — үргэлж нэгээр ялгаатай байх болно гэдгийг сана. Хэрэв бид блокийн эхний элементийг хасаад, түүнийг блокийн бусад зүйл бүрээс хасвал блок бүрийг $+1$ ба $-1$ тооноос тогтох $K - 1$ урттай дараалалаар тодорхойлж болно. Эдгээр блок маш жижиг тул гарч ирж болох ялгаатай дараалал цөөхөн байна. Боломжит дарааллын тоо нь:

$$2^{K-1} = 2^{0.5 \log(N) - 1} = 0.5 \left(2^{\log(N)}\right)^{0.5} = 0.5 \sqrt{N}$$

Ингэснээр ялгаатай блокийн тоо $O(\sqrt{N})$ бөгөөд тиймээс бид бүх ялгаатай блокуудын доторх интервал дахь хамгийн бага элементийн асуулгын үр дүнг $O(\sqrt{N} K^2) = O(\sqrt{N} \log^2(N)) = O(N)$ хугацаанд урьдчилан тооцоолж болно. Хэрэгжүүлэлтийн хувьд бид блокийг $K-1$ урттай битмаскаар (энэ нь стандарт int-д багтана) тодорхойлж, минимумын индексийг $O(\sqrt{N} \log^2(N))$ хэмжээтэй массив $\text{block}[\text{mask}][l][r]$-д хадгалж болно.

Ингэснээр бид блок бүрийн доторх интервал дахь хамгийн бага элементийн асуулга, мөн блокуудын интервал дээрх интервал дахь хамгийн бага элементийн асуулгыг бүгдийг $O(N)$-д хэрхэн урьдчилан тооцоолохыг сурлаа. Эдгээр урьдчилсан тооцооллоор бид хамгийн ихдээ дөрвөн урьдчилан тооцоолсон утгыг ашиглан асуулга бүрд $O(1)$-д хариулж чадна: l-г агуулсан блокийн минимум, r-г агуулсан блокийн минимум, мөн тэдгээрийн хоорондох блокуудын давхцах хэрчмүүдийн хоёр минимум.

Implementation

int n;
vector<vector<int>> adj;

int block_size, block_cnt;
vector<int> first_visit;
vector<int> euler_tour;
vector<int> height;
vector<int> log_2;
vector<vector<int>> st;
vector<vector<vector<int>>> blocks;
vector<int> block_mask;

void dfs(int v, int p, int h) {
    first_visit[v] = euler_tour.size();
    euler_tour.push_back(v);
    height[v] = h;

    for (int u : adj[v]) {
        if (u == p)
            continue;
        dfs(u, v, h + 1);
        euler_tour.push_back(v);
    }
}

int min_by_h(int i, int j) {
    return height[euler_tour[i]] < height[euler_tour[j]] ? i : j;
}

void precompute_lca(int root) {
    // get euler tour & indices of first occurrences
    first_visit.assign(n, -1);
    height.assign(n, 0);
    euler_tour.reserve(2 * n);
    dfs(root, -1, 0);

    // precompute all log values
    int m = euler_tour.size();
    log_2.reserve(m + 1);
    log_2.push_back(-1);
    for (int i = 1; i <= m; i++)
        log_2.push_back(log_2[i / 2] + 1);

    block_size = max(1, log_2[m] / 2);
    block_cnt = (m + block_size - 1) / block_size;

    // precompute minimum of each block and build sparse table
    st.assign(block_cnt, vector<int>(log_2[block_cnt] + 1));
    for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
        if (j == block_size)
            j = 0, b++;
        if (j == 0 || min_by_h(i, st[b][0]) == i)
            st[b][0] = i;
    }
    for (int l = 1; l <= log_2[block_cnt]; l++) {
        for (int i = 0; i < block_cnt; i++) {
            int ni = i + (1 << (l - 1));
            if (ni >= block_cnt)
                st[i][l] = st[i][l-1];
            else
                st[i][l] = min_by_h(st[i][l-1], st[ni][l-1]);
        }
    }

    // precompute mask for each block
    block_mask.assign(block_cnt, 0);
    for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
        if (j == block_size)
            j = 0, b++;
        if (j > 0 && (i >= m || min_by_h(i - 1, i) == i - 1))
            block_mask[b] += 1 << (j - 1);
    }

    // precompute RMQ for each unique block
    int possibilities = 1 << (block_size - 1);
    blocks.resize(possibilities);
    for (int b = 0; b < block_cnt; b++) {
        int mask = block_mask[b];
        if (!blocks[mask].empty())
            continue;
        blocks[mask].assign(block_size, vector<int>(block_size));
        for (int l = 0; l < block_size; l++) {
            blocks[mask][l][l] = l;
            for (int r = l + 1; r < block_size; r++) {
                blocks[mask][l][r] = blocks[mask][l][r - 1];
                if (b * block_size + r < m)
                    blocks[mask][l][r] = min_by_h(b * block_size + blocks[mask][l][r], 
                            b * block_size + r) - b * block_size;
            }
        }
    }
}

int lca_in_block(int b, int l, int r) {
    return blocks[block_mask[b]][l][r] + b * block_size;
}

int lca(int v, int u) {
    int l = first_visit[v];
    int r = first_visit[u];
    if (l > r)
        swap(l, r);
    int bl = l / block_size;
    int br = r / block_size;
    if (bl == br)
        return euler_tour[lca_in_block(bl, l % block_size, r % block_size)];
    int ans1 = lca_in_block(bl, l % block_size, block_size - 1);
    int ans2 = lca_in_block(br, 0, r % block_size);
    int ans = min_by_h(ans1, ans2);
    if (bl + 1 < br) {
        int l = log_2[br - bl - 1];
        int ans3 = st[bl+1][l];
        int ans4 = st[br - (1 << l)][l];
        ans = min_by_h(ans, min_by_h(ans3, ans4));
    }
    return euler_tour[ans];
}