Интервал дахь хамгийн бага элемент (RMQ)¶
Танд $A[1..N]$ массив өгөгдсөн. Та $(L, R)$ хэлбэрийн ирж буй асуулгуудад хариулах ёстой; эдгээр нь $A$ массив дахь $L$ ба $R$ байрлалын хооронд (заагийг оруулаад) орших хамгийн бага элементийг олохыг шаардана.
RMQ нь бодлогод шууд гарч ирж болох буюу бусад зарим бодлогод, жишээ нь Хамгийн бага нийтлэг өвөг бодлогод хэрэглэгдэж болно.
Шийдэл¶
RMQ бодлогыг бодоход ашиглаж болох олон арга, өгөгдлийн бүтэц бий.
Энэ сайтад тайлбарласан хувилбаруудыг доор жагсаав.
Эхлээд асуулгад хариулах хооронд массивыг өөрчлөхийг зөвшөөрдөг аргууд.
- Sqrt-задаргаа - асуулга бүрд $O(\sqrt{N})$-д хариулна, урьдчилсан боловсруулалт $O(N)$-д хийгдэнэ. Давуу тал: маш энгийн өгөгдлийн бүтэц. Сул тал: муу complexity.
- Хэрчмийн мод - асуулга бүрд $O(\log N)$-д хариулна, урьдчилсан боловсруулалт $O(N)$-д хийгдэнэ. Давуу тал: сайн time complexity. Сул тал: бусад өгөгдлийн бүтэцтэй харьцуулбал кодын хэмжээ их.
- Фенвикийн мод - асуулга бүрд $O(\log N)$-д хариулна, урьдчилсан боловсруулалт $O(N \log N)$-д хийгдэнэ. Давуу тал: хамгийн богино код, сайн time complexity. Сул тал: Фенвикийн модыг зөвхөн $L = 1$ байх асуулгад ашиглаж болох тул олон бодлогод хэрэглэх боломжгүй.
Дараа нь зөвхөн статик массив дээр ажилладаг, өөрөөр хэлбэл өгөгдлийн бүтцийг бүхэлд нь дахин тооцоолохгүйгээр массив дахь утгыг өөрчлөх боломжгүй аргууд.
- Сийрэг хүснэгт - асуулга бүрд $O(1)$-д хариулна, урьдчилсан боловсруулалт $O(N \log N)$-д хийгдэнэ. Давуу тал: энгийн өгөгдлийн бүтэц, маш сайн time complexity.
- Sqrt мод - асуулгад $O(1)$-д хариулна, урьдчилсан боловсруулалт $O(N \log \log N)$-д хийгдэнэ. Давуу тал: хурдан. Сул тал: хэрэгжүүлэхэд төвөгтэй.
- Огтлолцолгүй олонлогийн нэгдэл / Арпагийн заль мэх - асуулгад $O(1)$-д хариулна, урьдчилсан боловсруулалт $O(n)$-д. Давуу тал: богино, хурдан. Сул тал: зөвхөн бүх асуулга урьдчилан мэдэгдэж байвал ажиллана, өөрөөр хэлбэл зөвхөн асуулгыг офлайн боловсруулахыг дэмждэг.
- Декартын мод ба Фарах-Колтон-Бендерийн алгоритм - асуулгад $O(1)$-д хариулна, урьдчилсан боловсруулалт $O(n)$-д. Давуу тал: оновчтой complexity. Сул тал: кодын хэмжээ их.
Тэмдэглэл: Урьдчилсан боловсруулалт гэдэг нь өгөгдсөн массивт харгалзах өгөгдлийн бүтцийг байгуулах замаар түүнийг урьдчилан боловсруулах явдал юм.