Array-н хэсгүүдийн нийлбэрийг tree-д хадгалж, хэсгийн нийлбэр олох ба тоо өөрчлөх хоёуланг нь хурдан хийдэг бүтэц.

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

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

a = [3, 1, 4, 2] array өгөгдөв. Эхлээд a[1..3] хэсгийн нийлбэрийг асууя: 1 + 4 + 2 = 7. Дараа нь a[2] = 5 болгоод дахин асуухад 1 + 5 + 2 = 8.

Tree-д root нь [0..3] хэсгийн нийлбэр 10, хоёр child нь [0..1] = 4 ба [2..3] = 6. Эхний асуултад [1] leaf-ийн 1 ба [2..3] node-ын 6-г нэмэхэд л хангалттай.

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

Хамгийн энгийн арга бол асуулт бүрт l-ээс r хүртэл loop гүйлгэх. n = 100 000, асуулт 100 000 бол 10¹⁰ үйлдэл болж, хэт удаан. Prefix sum хурдан ч тоо өөрчлөгдөх бүрт бүх prefix-ийг дахин бодох хэрэгтэй болно.

Segment Tree array-г дахин дахин хоёр хувааж, хэсэг бүрийн нийлбэрийг node-д хадгална. Аливаа [l, r] хэсгийг ердөө 2 log n орчим бэлэн node-оор бүрдүүлж болно. Нэг тоо өөрчлөгдөхөд түүнийг агуулсан log n node л шинэчлэгдэнэ.

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

t[v]
v дугаартай node-ын хадгалах нийлбэр. Root нь v = 1, түүний child-ууд 2v ба 2v + 1.
l, r
v node-ын хариуцдаг хэсэг a[l..r]. Leaf бол l == r.
ql, qr
Асуусан хэсгийн зааг. Кодонд query(1, 0, n - 1, ql, qr) гэж дуудна.
build / update / query
Tree байгуулах, нэг тоо өөрчлөх, хэсгийн нийлбэр олох гурван recursive function.
res
Query-ийн хариуг хуримтлуулах хувьсагч. Асуулт бүрийн өмнө 0 болгоно.
?[0..7]?[0..3]?[4..7]?[0..1]?[2..3]?[4..5]?[6..7]?[0]?[1]?[2]?[3]?[4]?[5]?[6]?[7]

Array: 5 8 6 3 2 7 2 6. Node бүр нэг хэсгийн нийлбэрийг хадгална: root нь бүх тооных, leaf бүр ганц тооных. Эхлээд tree-г байгуулъя. Дараа нь a[3] = 10 болгоод, a[2..6] хэсгийн нийлбэрийг олно.

Алхам 1 / 28
Хурд
  • Одоогийн node
  • Бодсон node
  • Шинэчилсэн
  • Хувааж шалгасан
  • Хариунд нэмсэн
  • Хэрэггүй эсвэл бодоогүй
Слайд 1 / 6

Хэсгийн нийлбэрийг хурдан

a[l..r] хэсгийн нийлбэрийг олон удаа асуувал тоо бүрийг дахин нэмэх нь удаан. Segment Tree хэсгүүдийн нийлбэрийг tree-д хадгалдаг. Тиймээс асуултад ч, тоо өөрчлөхөд ч хурдан.

segment-tree.cpp
#include <bits/stdc++.h>
using namespace std;
int n, q, a[100005];
long long t[400005], res;
void build(int v, int l, int r) {
if (l == r) {
t[v] = a[l];
return;
}
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = t[2 * v] + t[2 * v + 1];
}
void update(int v, int l, int r, int i, int x) {
if (l == r) {
t[v] = x;
return;
}
int m = (l + r) / 2;
if (i <= m) {
update(2 * v, l, m, i, x);
} else {
update(2 * v + 1, m + 1, r, i, x);
}
t[v] = t[2 * v] + t[2 * v + 1];
}
void query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
res += t[v];
return;
}
int m = (l + r) / 2;
query(2 * v, l, m, ql, qr);
query(2 * v + 1, m + 1, r, ql, qr);
}
int main() {
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a[i];
build(1, 0, n - 1);
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) {
update(1, 0, n - 1, x, y);
} else {
res = 0;
query(1, 0, n - 1, x, y);
cout << res << '\n';
}
}
return 0;
}

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

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

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

1. Node бүр нэг хэсгийн нийлбэрийг хадгална: root нь бүх array-н, leaf бүр ганц тооны. 2. Байгуулах: хэсгийг дундуур нь хоёр хуваана. Node-ын утга нь хоёр child-ынх нь нийлбэр. Доороос дээш бөглөнө. 3. Өөрчлөх ("1 i x"): leaf хүртэл доошоо очиж a[i] = x болгоно. Буцахдаа замын node-уудыг дахин бодно. 4. Асуух ("2 l r"): node асуусан хэсэгт бүтэн багтвал нийлбэрийг нь шууд авна. Огт давхцахгүй бол алгасна. Хэсэгчлэн багтвал хоёр child руу нь орно. Оролт: эхний мөрөнд n ба q, дараагийн мөрөнд n тоо. Дараа нь q мөр: "1 i x" эсвэл "2 l r" (index 0-ээс эхэлнэ).

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

Node бүрийн утга нь хоёр child-ынх нь нийлбэр тул root-оос leaf хүртэл бүх утга зөв байна. update нь өөрчлөгдсөн leaf-ээс root хүртэлх замыг л буцахдаа дахин боддог. Бусад node-ын хэсэгт тэр тоо ордоггүй тул тэдгээр зөв хэвээр. query бүтэн багтсан node-ын утгыг шууд авч, давхцахгүй node-ыг алгасна. Тиймээс [ql, qr] доторх тоо бүр яг нэг удаа нэмэгдэнэ.

Tree-гийн гүн нь log₂ n орчим. update нэг замаар явдаг тул O(log n). query давхар бүрт ихдээ 4 node-д ордог тул мөн O(log n). n = 100 000 бол гүн нь 17, нэг асуултад хэдхэн арван node. build нь O(n), санах ой t[4n].

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

  • t array-г 2n хэмжээтэй зарлах. n нь 2-ын зэрэг биш үед node-ын дугаар 2n-ээс давж болно. 4n гэж зарла.
  • Асуулт бүрийн өмнө res = 0 болгохоо мартах. Өмнөх асуултын хариу нэмэгдэж үлдэнэ.
  • Нийлбэр int-ээс хэтрэх. 10⁵ тоо тус бүр 10⁹ хүртэл бол нийлбэр 10¹⁴ болно. long long ашигла.
  • Index 0-ээс эхэлж байгаа эсэхийг андуурах. Бодлого 1-ээс эхэлсэн index өгвөл l - 1, r - 1 болгож хөрвүүл.

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

  • n = 1: tree нь ганц leaf. build шууд t[1] = a[0] болгоно.
  • l == r: нэг тоог асуусан. Query тэр leaf хүртэл бууж, утгыг нь авна.
  • l = 0, r = n - 1: root бүтэн багтах тул нэг алхамд хариулна.
  • Ижил index-ийг олон удаа өөрчлөх: update бүр утгыг дарж бичнэ, нэмэхгүй.

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

  1. n = 8 бол tree-д нийт хэдэн node байх вэ?

    Хариу харах

    15. 8 leaf, 4 + 2 + 1 = 7 дотоод node. Ерөнхийдөө 2n − 1.

  2. a = [5, 8, 6, 3, 2, 7, 2, 6] дээр [0..7] хэсгийг асуухад хэдэн node-ын утгыг нэмэх вэ?

    Хариу харах

    1. Root бүтэн багтах тул t[1]-ийг шууд авна.

  3. Нэг update хийхэд n = 1024 бол хэдэн node-ын утга өөрчлөгдөх вэ?

    Хариу харах

    11. Leaf-ээс root хүртэлх замд log₂ 1024 + 1 = 11 node бий.

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

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

  1. 1.a = [2, 7, 1, 8] дээр tree байгуул. Node бүрийн утгыг бичээд a[0..2] хэсгийн нийлбэрийг ол.

    Hint харах

    Эхлээд [0..1] ба [2..3] хэсгийн нийлбэрийг ол.

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

    [0..1] = 9, [2..3] = 9, root = 18. Query нь [0..1]-ийн 9 ба [2] leaf-ийн 1-ийг нэмж 10 гэж хариулна.

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

    Hint харах

    +-ийг юугаар солих вэ? Давхцахгүй хэсэгт ямар утга буцаах вэ?

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

    t[v] = min(t[2 * v], t[2 * v + 1]) болгоно. query нь res = min(res, t[v]) хийж, эхэндээ res = INT_MAX байна. Үлдсэн бүтэц хэвээр.

  3. 3.Бүх тоо эерэг. Prefix нийлбэр нь анх удаа k-гээс багагүй болох хамгийн бага index-ийг O(log n)-д ол.

    Hint харах

    Root-оос эхэлж бууна. Зүүн child-ын нийлбэр k-д хүрэх үү?

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

    v = 1-ээс эхэлнэ. t[2v] >= k бол зүүн тийш бууна. Эс бөгөөс k -= t[2v] болгоод баруун тийш бууна. Leaf-д хүрэхэд түүний index хариу болно.

Жишээ

Оролт

8 3
5 8 6 3 2 7 2 6
2 2 6
1 3 10
2 2 6

Гаралт

20
27

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.