RMQ (интервал дахь хамгийн бага элемент)-г хамгийн бага нийтлэг өвөг (LCA) олох замаар бодох¶

A[0..N-1] массив өгөгдсөн. [L, R] хэлбэрийн асуулга бүрийн хувьд бид A массивын L байрлалаас эхэлж R байрлалаар төгсөх хэсэг дэх хамгийн багыг олохыг хүсэж байна. Бид A массив энэ явцад өөрчлөгдөхгүй гэж үзнэ, өөрөөр хэлбэл энэ өгүүлэлд статик RMQ бодлогын шийдийг тайлбарлана

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

Алгоритм¶

Бид A массиваас Декартын мод байгуулна. A массивын Декартын мод гэдэг нь модны дунд эрэмбээр тойролт зангилаануудад A массив дахь дараалалтай нь ижил дарааллаар зочилдог байх мин-овоолгын шинж чанартай (эцэг зангилааны утга хүүхдүүдийнхээ утгаас бага буюу тэнцүү байх ёстой) хоёртын мод юм.

Өөрөөр хэлбэл Декартын мод бол рекурсив өгөгдлийн бүтэц юм. A массивыг 3 хэсэгт хуваана: массивын хамгийн бага хүртэлх угтвар, хамгийн бага элемент, ба үлдсэн дагавар. Модны үндэс нь A массивын хамгийн бага элементэд харгалзах зангилаа байх ба зүүн дэд мод нь угтварын Декартын мод, баруун дэд мод нь дагаврын Декартын мод байна.

Дараах зурган дээр та 10 урттай нэг массив ба түүнд харгалзах Декартын модыг харж болно.

[l, r] интервал дахь хамгийн бага элементийн асуулга нь [l', r'] хамгийн бага нийтлэг өвгийн асуулгатай эквивалент бөгөөд энд l' нь A[l] элементэд харгалзах зангилаа, r' нь A[r] элементэд харгалзах зангилаа юм. Үнэндээ интервал дахь хамгийн бага элементэд харгалзах зангилаа нь интервал дахь бүх зангилааны, тиймээс l' ба r'-ийн ч өвөг байх ёстой. Энэ нь мин-овоолгын шинж чанараас автоматаар гарна. Мөн энэ нь хамгийн бага өвөг байх ёстой, учир нь эс бөгөөс l' ба r' хоёул зүүн эсвэл баруун дэд модонд байх байсан ба энэ нь зөрчил үүсгэнэ, учир нь ийм тохиолдолд хамгийн бага элемент интервалд ч байхгүй болно.

Дараах зурган дээр та [1, 3] ба [5, 9] RMQ асуулгуудын LCA асуулгуудыг харж болно. Эхний асуулгад A[1] ба A[3] зангилаануудын LCA нь 2 утгатай A[2]-т харгалзах зангилаа, хоёр дахь асуулгад A[5] ба A[9]-ийн LCA нь 3 утгатай A[8]-д харгалзах зангилаа юм.

Ийм модыг $O(N)$ хугацаанд байгуулж болох ба Фарах-Колтон, Бендерийн алгоритм модыг $O(N)$-д урьдчилан боловсруулж, LCA-г $O(1)$-д олж чадна.

Декартын мод байгуулах¶

Бид Декартын модыг элементүүдийг нэг нэгээр нь нэмэх замаар байгуулна. Алхам бүрд бид боловсруулсан бүх элементийн хүчинтэй Декартын модыг хөтөлнө. s[i] элемент нэмэх нь зөвхөн модны хамгийн баруун зам дахь — үндэснээс эхлээд баруун хүүхдийг дахин дахин авах — зангилаануудыг өөрчилж чадахыг харахад амархан. s[i]-ээс их буюу тэнцүү боловч хамгийн бага утгатай зангилааны дэд мод нь s[i]-ийн зүүн дэд мод болох ба s[i] үндэстэй мод нь s[i]-ээс бага боловч хамгийн их утгатай зангилааны шинэ баруун дэд мод болно.

Үүнийг хамгийн баруун зангилаануудын индексийг хадгалахад стек ашиглан хэрэгжүүлж болно.

vector<int> parent(n, -1);
stack<int> s;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!s.empty() && A[s.top()] >= A[i]) {
        last = s.top();
        s.pop();
    }
    if (!s.empty())
        parent[i] = s.top();
    if (last >= 0)
        parent[last] = i;
    s.push(i);
}