|
RMQ ning LCA ga qisqarishi.
Va endi kutilmagan burilish keladi. Biz RMQ +1 va -1 muammosining umumiy holatini LCA muammosiga qisqartiramiz. Va biz LCA muammosini RMQ muammosiga qanday kamaytirishni allaqachon bilamiz, biz buni O(n+q) da hal qila olamiz. Ya'ni, ma'lumotlarning bunday g'alati ketma-ketligi bilan biz O(n+q) da RMQ masalasining umumiy holatini yechish yo'llarini o'rganamiz.
Kamaytirishning o'zi ham juda g'alati va hayratlanarli ko'rinishi mumkin. Aytaylik, bizda A massiv bor. Dekart daraxtini quraylik, uning kalitlari 0 dan n-1 gacha bo'lgan sonlar, A massivning elementlari esa ustuvorlik (ildiz minimal element). Ya'ni, biz (i,A(i)) juftlikda Dekart daraxtini quramiz. Umuman olganda, O(n) da Dekart daraxtini qurish mumkin emas, chunki bu O(n) da massivni saralash masalasini hal qiladi, lekin bizning holatlarimizda kalitlar 0 dan n-1 gacha bo'lgan raqamlardir, shuning uchun ular allaqachon tartiblangan. Saralangan kalitlar holatida, O(n) da dekart daraxtini osongina qurish mumkin. Algoritmni keyinroq muhokama qilamiz.
Endi shuni ta'kidlash kerakki, l dan r gacha bo'lgan segmentdagi minimal qiymat bizning Dekart daraxtimizdagi l va r tugmachalari bilan cho'qqilarning LCA ga to'liq mos keladi. Haqiqatan ham, LCA koordinatada chap va o'ng pastki daraxtlar orasida joylashgan, ya'ni LCA kaliti l va r orasida joylashgan. Boshqa tomondan, LCA potentsiali uning pastki daraxtida minimaldir va bu pastki daraxt l dan r gacha bo'lgan barcha kichik segmentni o'z ichiga oladi, chunki u o'z chegaralarini o'z ichiga oladi. Shunday qilib, bu raqam kerakli segmentda yotadi va undagi minimaldir.
Kalitlar tartiblangan bo'lsa, O(n) da Dekart daraxtini qanday qurishni o'rganishgina qoladi. Daraxtga elementlarni kalitlarning o'sish tartibida ketma-ket qo'shamiz. Yangi kalit, albatta, daraxtning eng o'ngdagi tuguniga aylanadi. Uni qaerga osib qo'yishni va daraxtni qanday tiklashni aniqlashgina qoladi. Keling, biz qo'shgan oldingi cho'qqini ko'rib chiqaylik. Agar yangi cho'qqining potentsiali avvalgisining potentsialidan kam yoki unga teng bo'lsa, uni avvalgi cho'qqining o'ng tomoniga osib qo'yish kerak (chunki uning hali o'ng o'g'li yo'q). Agar yangi cho'qqining potentsiali oldingi cho'qqining potentsialidan kamroq bo'lsa, biz potentsiali yangi cho'qqining potentsialidan allaqachon katta yoki unga teng bo'lgan birinchi cho'qqiga duch kelgunimizcha undan ildiz tomon ko'tarilishimiz kerak. Daraxtga v cho'qqisini qo'shamiz, u cho'qqi v dan kam potentsialga ega va u ning otasi p potentsial v dan kam emas. Endi p cho'qqining o'ng bolasi v cho'qqi bo'ladi va u cho'qqi v cho'qqisining chap bolasi tomonidan osilgan bo'lishi kerak, ya'ni v cho'qqisi p --> u chekkasi ichida joylashgan. Agar bunday p cho'qqi bo'lmasa, ya'ni barcha cho'qqilar v dan kam potentsialga ega bo'lsa, u shunchaki yangi ildizga aylanadi va biz unga eski ildizni chap o'g'il sifatida osib qo'yamiz.
Butun jarayonni stek sifatida tasavvur qilish mumkin. Dekart daraxtining o'ng shoxini stekda saqlaylik. Bu stek pastlar stekiga juda o'xshaydi. Keyin, yangi tepa kelganda, biz elementlarni stekdan ularning potentsiallari yangi tepaning potentsialidan kam bo'lgunga qadar olib tashlaymiz, so'ngra daraxtda doimiy miqdordagi o'zgarishlarni amalga oshirib, stekga yangi tepa qo'shamiz. Har bir cho'qqi stekga bir marta qo'shilganligi sababli (va shuning uchun olib tashlangan) algoritmning asimptotik harakati O (n) dir.
Eslatma: Endi agar siz Tarjan algoritmining oʻzgarishidan foydalanib yechimga qaytsangiz, biz ishlatgan stek aslida Dekart daraxti qurish stegi ekanligini koʻrishingiz mumkin. Biroq, Tarjan algoritmining tuzilishi tufayli biz hech qanday daraxt qura olmaymiz va oddiyroq algoritmni olamiz.
Amaliyot uchun FKB algoritmining soddalashtirilgan bit o'zgarishi
Biz RMQ yechimining nazariy chiziqliligiga erishdik, biroq bu algoritmni uch xil faza tufayli amalga oshirish juda qiyin va asimptotik konstanta yetarlicha katta bo‘lib, bu algoritm amalda kamdan-kam qo‘llanilishi mumkin. Muammoning oflayn versiyasini hal qilishda, Tarjan algoritmining o'zgarishiga qarashga arziydi. Ko'pincha bu etarli bo'ladi.
Biroq, agar muammo hali ham onlayn tarzda hal qilinishi kerak bo'lsa, LCA ga ma'lumotsiz va RMQ +1 va -1 ga qaytib FKB algoritmining soddalashtirilgan.
Do'stlaringiz bilan baham: |
