Өөрчлөгддөггүй array-н дурын хэсгийн хамгийн бага тоог O(1) хугацаанд олдог хүснэгт.

Advanced & LegendХугацаа: O(n log n + q)Санах ой: O(n log n)

Эхлээд жижиг бодлого

a = [6, 2, 8, 5, 9, 1, 7, 4, 3, 8]. a[0..4] ба a[6..9] хэсгүүдийн хамгийн бага нь хэд вэ?

Эхний хэсэг 6, 2, 8, 5, 9 тул хамгийн бага нь 2. Хоёр дахь хэсэг 7, 4, 3, 8 тул 3. Хариу: 2, 3.

Энгийн аргаас санаа руу

Энгийн арга: query бүрт хэсгийг бүхэлд нь шалгана. q = n = 10⁵ бол 10¹⁰ алхам.

Гол санаа: урт нь 2-ын зэрэг байх бүх хэсгийн хамгийн багыг урьдчилан бодож хадгална. Дурын [l, r] хэсгийг ижил урттай хоёр ийм хэсгээр бүтэн хучиж болно. Тэд давхцаж болно, гэхдээ min-д давхцал нөлөөлөхгүй. Тиймээс query бүрт хоёр нүд л харна.

Нэр томьёо ба тэмдэглэгээ

st[j][i]
a[i..i + 2^j - 1] хэсгийн хамгийн бага тоо.
lg[x]
2^j ≤ x байх хамгийн том j. lg[5] = 2.
RMQ
Range Minimum Query: хэсгийн хамгийн бага тоог асуух query.
idempotent
f(x, x) = x байх үйлдэл: min, max, gcd. Давхцал зөвхөн ийм үйлдэлд нөлөөлөхгүй.
урт \ i01234567891
6
2
8
5
9
1
7
4
3
8
2
4
8

Array: 6 2 8 5 9 1 7 4 3 8. st[j][i] нь i index-ээс эхэлсэн 2^j урттай хэсгийн хамгийн бага тоо. Эхний мөр нь array өөрөө. Бусад мөрийг өмнөх мөрөөс нь бөглөнө.

Алхам 1 / 24
Хурд
  • Шинэ нүд
  • Хоёр хагас
  • Асуусан хэсэг
  • Хариунд ашиглах нүд
  • Хараахан бөглөөгүй
Слайд 1 / 6

Хамгийн бага тоог шууд

Array өөрчлөгдөхгүй, харин "a[l..r] хэсгийн хамгийн бага нь хэд вэ?" гэсэн query олон ирнэ. Sparse Table бэлтгэлээ нэг удаа хийгээд, query бүрт O(1) хугацаанд хариулна.

sparse-table.cpp
#include <bits/stdc++.h>
using namespace std;
int n, q, lg[100005], st[17][100005];
int main() {
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> st[0][i];
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
while (q--) {
int l, r;
cin >> l >> r;
int j = lg[r - l + 1];
cout << min(st[j][l], st[j][r - (1 << j) + 1]) << '\n';
}
return 0;
}

Юунд хэрэгтэй вэ?

Array өөрчлөгдөхгүй, харин "a[l..r] хэсгийн хамгийн бага нь хэд вэ?" гэсэн query маш олон ирэхэд query бүрт шууд хариулна (RMQ). LCA, suffix array зэрэгт туслах хэрэгсэл болдог.

Яаж ажилладаг вэ?

1. st[j][i] нь i index-ээс эхэлсэн 2^j урттай хэсгийн хамгийн бага тоо. st[0] мөр нь array өөрөө. 2. Бөглөх: 2^j урттай хэсэг 2^(j − 1) урттай хоёр хагаснаас бүрдэнэ. Тэгэхээр st[j][i] = min(st[j − 1][i], st[j − 1][i + 2^(j − 1)]). 3. lg[x] бол 2^j ≤ x байх хамгийн том j. 4. Query [l..r]: j = lg[r − l + 1] гэж олно. l-ээс эхэлсэн, r дээр төгссөн 2^j урттай хоёр хэсгийн багыг авна. Хоёр хэсэг давхцаж болох ч хамгийн бага тоонд нөлөөлөхгүй. Оролт: эхний мөрөнд n ба q, дараагийн мөрөнд n тоо, дараа нь q мөр "l r". Index 0-ээс эхэлнэ.

Яагаад зөв, хэр хурдан бэ?

2^j урттай хэсэг 2^(j − 1) урттай хоёр хагасаас бүрддэг тул st[j][i] зөв бөглөгдөнө. Query-д j = lg[len] бол 2^j ≤ len < 2^(j + 1). Тиймээс l-ээс эхэлсэн ба r дээр дуусах хоёр хэсэг нийлээд [l, r] хэсгийг бүтэн хучна, гадуур гарахгүй.

Бөглөх O(n log n), query бүр O(1). n = 10⁵ бол 1.7 сая нүд бөглөөд, 10⁵ query-д 10⁵ орчим алхам хийнэ.

Түгээмэл алдаа

  • Нийлбэрт ашиглах. Давхцсан тоонууд хоёр удаа тоологдоно. Нийлбэрт prefix sum хэрэглэ.
  • Хүснэгтийн мөр хүрэлцэхгүй байх. n = 10⁵ бол j нь 16 хүртэл, тиймээс 17 мөр хэрэгтэй.
  • log2() функцийг double-аар бодох. Бутархайн алдаанаас болж буруу j гарч болно. lg array эсвэл __lg(len) ашигла.
  • Баруун хэсгийн эхлэлийг r - (1 << j) гэж бичих. Зөв нь r - (1 << j) + 1.

Хязгаарын тохиолдол

  • l = r: урт 1, j = 0, хариу a[l].
  • Урт яг 2^j: хоёр хэсэг бүрэн давхцана, ганц нүд л хэрэгтэй.
  • Бүх array: [0, n − 1] ч хоёр нүдээр шийдэгдэнэ.
  • n = 1: хүснэгт ганц мөртэй.

Өөрийгөө шалга

  1. lg[10] хэд вэ?

    Хариу харах

    3. 2³ = 8 ≤ 10 < 16.

  2. [2..8] query-д аль хоёр нүдийг харах вэ?

    Хариу харах

    st[2][2] ба st[2][5]. Урт нь 7 тул j = 2.

  3. Яагаад Sparse Table ашиглан нийлбэр бодож болохгүй вэ?

    Хариу харах

    Хоёр хэсэг давхцвал давхцсан тоонууд хоёр удаа нэмэгдэнэ.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [5, 3, 7, 1, 4] дээр st хүснэгтийг бүтэн бөглө.

    Hint харах

    Мөр бүрийг өмнөх мөрөөс нь бөглө.

    Хариу ба тайлбар

    j = 0: 5 3 7 1 4. j = 1: 3 3 1 1. j = 2: 1 1.

  2. 2.Кодыг хэсгийн хамгийн их тоог олдог болго.

    Hint харах

    Зөвхөн нэг function солигдоно.

    Хариу ба тайлбар

    Хоёр газар min гэснийг max болгоно. Үлдсэн код хэвээр.

  3. 3.Хэсгийн бүх тооны GCD-г O(1) хугацаанд ол.

    Hint харах

    gcd(x, x) = x тул давхцал нөлөөлөхгүй.

    Хариу ба тайлбар

    min функцийн оронд __gcd ашиглан яг ижил хүснэгт байгуулна. Query: __gcd(st[j][l], st[j][r - (1 << j) + 1]).

Жишээ

Оролт

10 2
6 2 8 5 9 1 7 4 3 8
0 4
6 9

Гаралт

2
3