Array-г √n урттай блокуудад хувааж, хэсгийн нийлбэр олох ба тоо өөрчлөхийг хурдан хийдэг энгийн арга.

IntermediateХугацаа: O(n + q√n)Санах ой: O(n)

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

a = [3, 1, 4, 1, 5, 9, 2, 6, 5]. a[1..7] хэсгийн нийлбэр хэд вэ? Дараа нь a[4] = 2 болгоод дахин асууя.

Эхлээд 1 + 4 + 1 + 5 + 9 + 2 + 6 = 28. a[4] нь 5-аас 2 болж 3-аар багасна, тиймээс 25. Хариу: 28, 25.

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

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

Гол санаа: array-г b ≈ √n урттай блокуудад хувааж, блок бүрийн нийлбэрийг s-д хадгална. Query-д бүтэн багтах блокуудын нийлбэрийг шууд авна. Зөвхөн хоёр захын тоонуудыг нэг нэгээр нь нэмнэ. Тоо өөрчлөхөд ганц блокийн нийлбэрийг засна.

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

b
Блокийн урт, sqrt(n). n = 9 бол 3.
s[k]
k-р блокийн нийлбэр. a[i] нь i / b дугаартай блокт орно.
зах
Хэсгийн хоёр төгсгөлд, бүтэн багтаагүй блокуудын тоонууд.
res
Query-д хариулах нийлбэр.
a
3
0
1
1
4
2
1
3
5
4
9
5
2
6
6
7
5
8
блок
0
0
0
1
0
2
1
3
1
4
1
5
2
6
2
7
2
8
s
0
0–2
0
3–5
0
6–8
b = 3

Array: 3 1 4 1 5 9 2 6 5. 9 тоог 3 ширхгээр нь блок болгоно: b = ⌊√9⌋ = 3. s[k] нь k-р блокийн нийлбэр. Эхлээд блокуудын нийлбэрийг бодъё.

Алхам 1 / 17
Хурд
  • Одоогийн тоо
  • Шинэчилсэн
  • Ганцаар нь нэмсэн
  • Блокоороо нэмсэн
  • Ашигласан блок
Слайд 1 / 6

Блокуудад хуваая

n тоог √n ширхгээр нь блок болгоно. 9 тоо байвал 3 тоотой 3 блок. Блок бүрийн нийлбэрийг s array-д хадгална.

sqrt-decomposition.cpp
#include <bits/stdc++.h>
using namespace std;
int n, q, b, a[100005];
long long s[100005], res;
int main() {
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a[i];
b = sqrt(n);
for (int i = 0; i < n; i++) {
s[i / b] += a[i];
}
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) {
s[x / b] += y - a[x];
a[x] = y;
} else {
int l = x, r = y;
res = 0;
while (l <= r && l % b != 0) {
res += a[l++];
}
while (l + b - 1 <= r) {
res += s[l / b];
l += b;
}
while (l <= r) {
res += a[l++];
}
cout << res << '\n';
}
}
return 0;
}

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

a[l..r] хэсгийн нийлбэр олох, a[i]-г өөрчлөх query холилдон ирэхэд query бүрт O(√n) хугацаанд хариулна. Санаа нь энгийн тул Segment Tree бичихэд төвөгтэй олон төрлийн бодлогод тохирно.

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

1. b = √n. a[i] нь i / b дугаартай блокт орно. s[k] бол k-р блокийн нийлбэр. 2. Өөрчлөх ("1 i x"): блокийн нийлбэрт хуучин ба шинэ утгын зөрүүг нэмээд a[i] = x болгоно. 3. Асуух ("2 l r"): зүүн захын бүтэн биш блокийн тоонуудыг нэг нэгээр нь, дундах бүтэн блокуудыг s-ээс шууд, баруун захын тоонуудыг дахин нэг нэгээр нь нэмнэ. 4. Зах бүрт b-гээс цөөн тоо, дунд нь n / b-гээс цөөн блок байх тул нийт O(√n). Оролт: эхний мөрөнд n ба q, дараагийн мөрөнд n тоо, дараа нь q мөр: "1 i x" эсвэл "2 l r". Index 0-ээс эхэлнэ.

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

Эхний loop l-ийг блокийн эхлэл болтол урагшлуулна. Дараа нь бүтэн блокууд, эцэст нь үлдсэн тоонууд нэмэгдэнэ. Хэсгийн тоо бүр яг нэг удаа нэмэгдэнэ: эсвэл ганцаараа, эсвэл блокийнхоо нийлбэрт орж.

Зах бүрт b-гээс цөөн тоо, дунд нь n / b-гээс цөөн блок. b = √n бол query бүр 3√n орчим алхам. n = 10⁵ бол 950 орчим, 10⁵ query-д 10⁸ хүрэхгүй. Өөрчлөх O(1).

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

  • Зөрүүг хуучин утгаа дарж бичсэний дараа бодох. Эхлээд s[x / b] += y - a[x], дараа нь a[x] = y.
  • Нийлбэрийг int-д хадгалах. 10⁵ тоо, тус бүр 10⁹ бол 10¹⁴ хүрнэ, long long хэрэгтэй.
  • l, r нэг блок дотор байх үед бүтэн блок байхгүй. Эхний loop l <= r нөхцөлтэй байх ёстой, үгүй бол r-аас хэтэрнэ.
  • Сүүлийн блок богино байж болно. s array-г n / b + 1 хэмжээтэй болго.

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

  • l = r: ганц тоо, аль нэг захын loop-оор нэмэгдэнэ.
  • Бүх array: бүх бүтэн блок шууд нэмэгдэнэ. Сүүлийн блок богино бол түүний тоонууд захаар нэмэгдэнэ.
  • Нэг блок дотор, жишээ нь [1, 2], b = 3: зөвхөн зүүн захын loop ажиллана.
  • Утга нь өөрчлөгдөхгүй update, a[i] аль хэдийн x: зөрүү 0, юу ч өөрчлөгдөхгүй.

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

  1. n = 16 бол хэдэн блок, тус бүр хэдэн тоотой вэ?

    Хариу харах

    4 блок, тус бүр 4 тоо.

  2. n = 9, query [2, 7] бол аль хэсэг нь блокоороо нэмэгдэх вэ?

    Хариу харах

    a[3..5] буюу 1-р блок. a[2], a[6], a[7] ганцаараа нэмэгдэнэ.

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

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

  1. 1.a = [2, 7, 1, 8, 2, 8, 1, 8] дээр [1, 6] query-г алхам алхмаар бод.

    Hint харах

    n = 8 тул b = 2. Блокийн нийлбэрүүд: 9, 9, 10, 9.

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

    a[1] = 7-г ганцаар нь (res = 7), 1-р блокийг (res = 16), 2-р блокийг (res = 26), a[6] = 1-ийг ганцаар нь нэмнэ. Хариу 27.

  2. 2.Нийлбэрийн оронд хэсгийн хамгийн бага тоог ол. Update ч бас ирнэ.

    Hint харах

    Нэг тоо өөрчлөгдөхөд блокийн хамгийн багыг зөрүүгээр засаж болох уу?

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

    s[k]-д блокийн хамгийн багыг хадгална. Query адилхан, нэмэхийн оронд min авна. Update хийсний дараа тэр блокийн хамгийн багыг бүтнээр нь дахин бодно: O(√n).

  3. 3.a[l..r] хэсгийн бүх тоонд x нэмдэг update нэм.

    Hint харах

    Бүтэн блокийн тоо бүрийг биш, блокийн "нэмэлт"-ийг хадгал.

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

    add[k] array нэмнэ. Бүтэн блокт add[k] += x, s[k] += x * b. Захын тоонд a[i] += x, s[i / b] += x. Query-д бүтэн блок s[k], захын тоо a[i] + add[i / b]. Сүүлийн блок богино бол b-гийн оронд жинхэнэ уртыг нь ашигла.

Жишээ

Оролт

9 3
3 1 4 1 5 9 2 6 5
2 1 7
1 4 2
2 1 7

Гаралт

28
25