Samarqand davlat universiteti raqamli texnologiyalar fakulteti amaliy matematika yo

Ba’zi hollarda biz xoxlaganday har doim ham masalani kodini yozishda bir turdan ikkinchi turga tulaligicha utmaydi, bunday holda RMQ ni LCA ga kamaytirishga harakat qilamiz. Endi biz LCAni tezda qanday hal qilishni bilishimiz kerak. Ajablanarlisi shundaki, biz buni kamaytirish orqali qilamiz LCA RMQ ga qaytdi! Ayyorlik shundaki, biz uni RMQ ning maxsus holatiga qisqartiramiz, biz uni chaqiramiz “RMQ±1”. RMQ±1 odatdagi RMQ bilan bir xil, faqat roʻyxatdagi qoʻshni qiymatlar faqat ±1 ga farq qiladi. Muammoni shakllantirish Birinchidan, muammo bayonotiga aniqlik kiritamiz. Maqola sarlavhasidagi statik so'z nimani anglatadi? RMQ muammosi ba'zan massiv elementlarini o'zgartirish qobiliyati bilan yuzaga keladi. Ya'ni, minimalni olish so'rovi elementni o'zgartirish yoki hatto segmentdagi elementlarni o'zgartirish qobiliyatiga qo'shiladi. .Har bir dasturning oz vazifasi boladi FKB algaritimi daraxtning eng kichik ajdodini topadi.Bu algaritim

Farak-Kolton va Bender algoritmi
RMQ (Range Minimum Query) vazifasi shundan iboratki, kirish n uzunlikdagi massiv va q so‘rovlar (ushbu massivning segmentlari) bo‘lib, har bir so‘rov uchun massivning mos segmentida minimumni topish zarur. Ushbu muammoni hal qilish uchun ko'plab yondashuvlar mavjud. da ishlaydigan soqov yechim bor, O(n+qlogn) da ishlaydigan segment daraxti yechimi bor, O(nlogn+q) da ishlaydigan siyrak jadval yechimi mavjud va hokazo. Ushbu maqolada biz ushbu muammoni hal qilish uchun zarur bo'lgan yondashuvni (masalan, segment daraxti deyarli har qanday operatsiya uchun qo'llaniladi) chiziqli vaqtda ishlaydigan yondashuvni, shuningdek, amalga oshirish osonroq bo'lgan muqobil yondashuvni ko'rib chiqamiz. va amalda tezroq.
Shuni ta'kidlash kerakki, ushbu vazifani ikkita shaklda bajarish mumkin: oflayn va onlayn. Oflayn rejimda barcha so'rovlar oldindan berilganligini anglatadi va siz ularga istalgan tartibda javob topishingiz mumkin. Biroq, topshiriqning onlayn versiyasida keyingi so'rov faqat oldingisiga javob berilgandan keyin beriladi. Muammoning ikkala versiyasini ham ko'rib chiqamiz.
Bundan tashqari, bu vazifani statik va dinamik versiyalarga bo'lish mumkin. Statik versiyada massiv tuzatilgan bo'lsa, dinamik versiyada massivni o'zgartirish uchun so'rovlar kelishi mumkin. Biz vazifaning statik versiyasini ko'rib chiqamiz.
RMQ oflayn. Tarjan algoritmining O(a(n)) da har bir soʻrov boʻyicha oʻzgarishi.
Bir qarashda, bu unchalik tushunarli bo‘lmasligi mumkin, ammo bu algoritm Tarjanning daraxtda LCA ni topishning asl algoritmi bilan juda qiziqarli aloqaga ega. Farah-Kolton va Bender (FKB) algoritmini tahlil qilganimizda bu ikki algoritm oʻrtasidagi chuqurroq bogʻliqlik aniq boʻladi, ammo hozircha bu algoritmni mustaqil deb hisoblashingiz mumkin.