Lca va statik rmq o'rtasidagi munosabat

LCA va statik RMQ o'rtasidagi munosabat.

Masalalarning katta sinfi uchun quyidagi yordamchi masalani yechish talab etiladi.

Vazifa. Ildizli daraxt beriladi. U_iui va v_ivi cho'qqilarining eng kichik umumiy ajdodini, ya'ni ildizdan u_iuigacha bo'lgan yo'lda, ildizdan v_ivigacha bo'lgan yo'lda joylashgan ww cho'qqisini topish uchun so'rovlarga javob berish talab etiladi. vaqt shu kabilarning eng chuquri (eng pasti).
Ingliz tilida bu muammo eng kam umumiy ajdod - eng kam umumiy ajdod deb ataladi.

Vertex ii - kk va nn uchlari uchun LCA
Yaxshiroq tushunish uchun - asta-sekin (chiziqli vaqt ichida) eng kichik umumiy ajdodni quyidagicha qidirish mumkin:
bool ancestor(int u, int v) {
return tin[u] <= tin[v] && tin[v] < tout[u];
}

int lca(int u, int v) {

while (!ancestor(u, v))
u = p[u];
return u;
}
Uni hal qilishning turli xil usullari mavjud va keyinroq ushbu bobda biz asosiylarini ko'rib chiqamiz. Xususan, ushbu maqolada biz uni segmentdagi minimalni topish muammosiga qisqartiramiz (va aksincha).
Statik RMQ ga qisqartirish
Keling, dfs bilan daraxt bo'ylab yuramiz va ikkita massivni yozamiz: cho'qqilarning chuqurligi va uchlari raqamlari. Biz ularni tepaga kirishda ham, chiqishda ham yozamiz.

Endi so'rov kirsin: vv va uu cho'qqilarining LCA ni toping. Aniqlik uchun vv ga aylanib o'tishda avvalroq duch kelgan deb faraz qilaylik: tin_v Aniqlanishicha, LCA ni topish uchun chuqurliklar massividagi (birinchi yozilgan massiv) [tout_v, tin_u] [toutv, tinu] segmentidagi minimal o‘rnini topib, uning qaysi cho‘qqiga mos kelishini ko‘rish mumkin. Euler traversal (ikkinchi yozilgan massiv). Shunday qilib, LCA muammosi RMQ muammosiga (segment bo'yicha minimalni topish) qisqartirilishi mumkin, buni, masalan, har bir so'rov uchun O (\ log n) O (logn) segmentlari daraxti bilan bajarish mumkin.
So'rov vaqtining asimptotikasi biz statik RMQ muammosini hal qilayotganimizdan foydalanib, yaxshilanishi mumkin, ya'ni bizda massiv o'zgarishlari yo'q. Buning uchun ko'proq mos tuzilma mavjud - siyrak jadval, bu so'rovga minimal O (1) O (1) da javob berishga imkon beradi, lekin O (n \ log n) O (nlogn) operatsiyalari va xotirani oldindan qayta ishlashdan foydalanadi. kichik konstanta.
Ma'lum bo'lishicha, siz uni oldinga va orqaga kamaytirishingiz mumkin.

Farak-Kolton va Bender algoritmi

Rad etish: Ushbu bo'limd a tasvirlangan LCA ni topish algoritmi amalda mutlaqo foydasiz, ammo nazariy nuqtai nazardan juda qiziq.
Ma'lum bo'lishicha, LCA ham, statik RMQ ham har bir so'rov bo'yicha O (1) O (1) vaqt va oldindan hisoblash uchun O (n) O (n) vaqtida hisoblanishi mumkin.
Aslida, LCA ni RMQ ga kamaytirishda biz to'liq bo'lmagan RMQ muammosini hal qilmoqdamiz. Biz 1 dan nn gacha bo'lgan barcha butun sonlar massivlari bilan ishlamaymiz, lekin faqat ba'zilari bilan - har qanday ikkita element aniq bitta bilan farq qiladiganlar bilan ishlaymiz, chunki har bir o'tish dfs da tushish yoki ko'tarilishdir. Ushbu cheklash sizga bunday massivlarning kichik segmentlarida minimalni tezroq topish imkonini beradi.
Oldindan hisoblash
Keling, quyidagilarni bajaramiz: har bir element oldingisidan bittaga ko'p yoki bitta kichik bo'lganligi sababli, biz asl chuqurlik massivini o'lchamdagi (n - 1) (n - 1) mantiqiy massiv bilan moslashtiramiz: biri o'lchamdagi bo'ladi. ii-pog'ona, agar keyingi qiymat katta bo'lsa, nol, kamroq bo'lsa. Ushbu massiv ikkilik shaklda saqlanishi kerak, shunda siz doimiy sifatida kichik segmentlarning mantiqiy niqobini olishingiz mumkin.
Oldindan hisoblashning birinchi qismi. k = \ lfloor \ frac {\ log n} {2} \ rfloork = ⌊2logn⌋ doimiysini oling va asl massivni kk elementlar bloklariga ajrating. Keling, har bir blok bo'yicha minimumni hisoblab chiqamiz va bu minimumlardan yuqori siyrak jadval tuzamiz.
Bunday bloklarning umumiy bloklari O (\ frac {2 n} {\ log n}) O (logn2n) dir va shuning uchun qurilish chiziqli vaqtda ishlaydi:
O (\ frac {2 n} {\ log n} \ log \ frac {2 n} {\ log n}) = O (\ frac {2 n} {\ log n} (\ log 2n - \ log \ log) n)) = O (n) O (logn2nloglogn2n) = O (logn2n (log2n - loglogn)) = O (n) Oldindan hisoblashning ikkinchi qismi. Keling, kk o'lchamdagi har bir mumkin bo'lgan ko'tarilish / tushish niqobi uchun unga maksimal tushishni hisoblab chiqamiz - ya'ni biz nol va duch kelganlar o'rtasidagi farqni saqlab, u orqali o'tamiz va ushbu muvozanatning minimal qiymatini eslaymiz. Bu ularning soniga ko'paytiriladi niqob uzunligi uchun amalga oshirilishi mumkin: O (k \ cdot 2 ^ k) = O (\ frac {\ log n} {2} 2 ^ {\ frac {\ log n} {2} }) = O (\ sqrt n \ log n) O (k⋅2k) = O (2logn22logn) = O (nlogn)
Mumkin bo'lgan niqoblar ko'p emas - buning uchun kk ni aniqlashda logarifmni ikkiga bo'ldik
So'rovga javob bering
Endi biz [l, r] [l, r] segmentida RMQ ni topish uchun hisoblangan tuzilmalardan foydalanishimiz kerak. U bir nechta ketma-ket bloklarni va chap va o'ngdagi ba'zi qolgan hujayralarni o'z ichiga oladi, ular hech qanday butun blokga kiritilmagan.
• Blok qismi uchun biz faqat siyrak jadvalda so'rov qilishimiz mumkin - u doimiy uchun ishlaydi.
• Ikkala bloklanmagan qismlar uchun ham javob uchun nomzodni hisoblaymiz. Buning uchun chegara elementiga qolgan bloklanmagan elementlarning niqobidagi minimalning oldindan hisoblangan qiymatini qo'shing - uni mantiqiy massivda bit operatsiyalari orqali doimiy sifatida olish mumkin.
Afsuski, ikkinchi holatni hal qilish uchun barcha bloklar uchun barcha qo'shimchalar va prefikslar minimallarini oddiygina hisoblab bo'lmaydi - so'rov kichik bo'lsa va hech qanday blokni to'liq qamrab olmasa, bitta alohida holat mavjud. Bunday holda, siz shunchaki chegara elementini olishingiz va unga balandliklar qatoridan kerakli niqobning minimalini qo'shishingiz kerak.
Statik RMQ → LCA
Bu algoritm nazariy nuqtai nazardan juda muhim, chunki u nafaqat LCA ni, balki umumiy holatda chiziqli oldindan hisoblash va har bir so'rov uchun doimiy statik RMQni ham echishga imkon beradi.
Keling, x_ixi kalitlari sifatida elementlarning indekslarini va y_iyi ustuvorliklari sifatida qiymatlarni qabul qiladigan Dekart daraxtini quraylik. Dekart daraxti muvozanatsiz bo'lib chiqishi mumkin (chunki ustuvor randomizatsiya yo'q), lekin bizga bu kerak emas. Keyin biz shunchaki yuqorida tavsiflangan algoritmni ushbu daraxtga qo'llaymiz va endi asl massivda minimalni topish uchun siz shunchaki daraxtdagi ll va rr uchlarning umumiy ajdodini so'rashingiz mumkin - uning Dekart daraxtidagi ustuvorligi bo'ladi. talab qilinadigan minimal.
Biroz batafsilroq va amalga oshirish bilan (muallif buni hech qachon kodlamagan va sizga maslahat bermaydi) Emaks-da o'qilishi mumkin. Biroq, amalda, bu algoritm katta konstanta tufayli foydalanish uchun amaliy emas: asimptotikada logarifmdan qutulish uchun hisoblash uchun juda ko'p narsa bor.