სეგმენტების ხე

პრეფიქსული ჯამები შუალედის ჯამს O(1)-ში გვაძლევს, მაგრამ მასივის შეცვლისას მათი თავიდან აგება O(n) ღირს. სეგმენტების ხე შუალედის მოთხოვნასაც და განახლებასაც O(log n)-ში ასრულებს. ამიტომაა ის რეიტინგულ ცხრილებში, მონიტორინგის პანელებსა და ოლიმპიადის ამოცანების ნახევარში.

მოწინავე⏱ 15 წთ

←ეყრდნობა

5ფენვიკის ხე (ბინარული ინდექს-ხე)ფენვიკის ხე პრეფიქსის ჯამებს პასუხობს; სეგმენტების ხე ნებისმიერ [L, R] ინტერვალზე მინიმუმსა და მაქსიმუმსაც პოულობს, რაც ფენვიკს არ შეუძლია.5ხეები: ცნებები, თვისებები, შემოვლებისეგმენტების ხე ორობითი ხეა, რომლის ყოველი წვერო ერთ შუალედს ფარავს.

გზას უხსნის→

აქ გზამკვლევი სრულდება. გადახედე, რა გზა გაიარე.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01შუალედების ჯამების ხე

მასივი სრული ორობითი ხის ფოთლებში ჩავწეროთ. ყოველი შიდა წვერო თავისი ორი შვილის ჯამს ინახავს, ამიტომ ყოველი წვერო ერთ უწყვეტ შუალედზეა პასუხისმგებელი: სათავე მთელ მასივს ფარავს, მისი შვილები ნახევრებს და ა.შ.

sum(l..r)-ზე საპასუხოდ ავიღოთ ის რამდენიმე წვერო, რომელთა შუალედები მთლიანად [l, r]-შია და ერთად ზუსტად ფარავს მას. ყოველ დონეზე ასეთი მაქსიმუმ ორია, ამიტომ მოთხოვნა O(log n) წვეროს ეხება.

ნახაზზე sum(2..6) იყენებს წვეროებს [2–3], [4–5] და [6]: სამი წვერო ხუთი რიცხვის ნაცვლად. მილიონ ელემენტზე ეს დაახლოებით 40 წვეროა მილიონის ნაცვლად.

ხე 4n ზომის მასივში შევინახოთ: v წვეროს შვილებია 2v და 2v+1, როგორც ორობით გროვაში. (ზუსტად 2n მხოლოდ მაშინ კმარა, როცა n ორის ხარისხია, ან იტერაციული, ქვემოდან ზემოთ აგებული ვარიანტისთვის.)

ყოველ წვეროზე მისი ჯამია, ქვემოთ კი შუალედი, რომელსაც ფარავს.

02წერტილოვანი განახლება და სხვა ოპერაციები

a[i]-ის შესაცვლელად განვაახლოთ მისი ფოთოლი, შემდეგ კი ავიდეთ სათავემდე და ყოველი წინაპარი თავიდან დავთვალოთ, როგორც ორი შვილის ჯამი. იცვლება მხოლოდ ამ გზაზე მყოფი log n + 1 წვერო.

აქ არაფერი არ არის მიბმული +-ზე. ნებისმიერი ასოციაციური ოპერაცია გამოდგება: მინიმუმი, მაქსიმუმი, უსგ, xor, ქვემასივის მაქსიმალური ჯამიც კი, თუ წვერო რამდენიმე დამატებით რიცხვს შეინახავს. შეცვალე გაერთიანების ფუნქცია, დანარჩენი იგივე რჩება.

ზარმაცი გავრცელებით (lazy propagation) წვეროს შეუძლია მთელი შუალედისთვის გადადებული განახლება დაიმახსოვროს („[l, r]-ს ყველა ელემენტს დაუმატე 5“) და ქვემოთ მხოლოდ საჭიროებისას გადასცეს. ასე შუალედის განახლებაც O(log n) ხდება. ჯერ საბაზისო ვერსია აითვისე.

03რეალიზაცია: რეკურსიული ვარიანტი

ოლიმპიადებში ჩვეულებრივ რეკურსიულ ვარიანტს წერენ. build(v, l, r): თუ l == r, ვინახავთ a[l]-ს; სხვა შემთხვევაში ვაგებთ ორივე ნახევარს m = (l + r) / 2-ზე და ვწერთ t[v] = t[2v] + t[2v+1].

query(v, l, r, ql, qr)-ს სამი შემთხვევა აქვს:

[l, r] მთლიანად [ql, qr]-ის გარეთაა: ვაბრუნებთ 0-ს;
[l, r] მთლიანად [ql, qr]-ის შიგნითაა: მაშინვე ვაბრუნებთ t[v]-ს;
სხვა შემთხვევაში: ვაბრუნებთ ორივე შვილის ჯამს.

update(v, l, r, i, x) ეშვება i-ს ფოთლამდე და უკან ამოსვლისას თავიდან ითვლის t[v]-ს. ყოველი გამოძახება O(log n) ღირს.

თუ მხოლოდ ჯამები და წერტილოვანი განახლება გჭირდება, საკმარისია უფრო მოკლე ფენვიკის ხე, რომელსაც ხეების ეტაპზე ცალკე გაკვეთილი აქვს; სეგმენტების ხე კი მაშინ გჭირდება, როცა მინიმუმი, მაქსიმუმი ან სხვა რამ გაინტერესებს, რისი „გამოკლებაც“ შეუძლებელია.

ფასი ერთი შეხედვით

აგებაO(n)

შუალედის მოთხოვნაO(log n)

წერტილოვანი განახლებაO(log n)

მეხსიერებაO(n)

დაიმახსოვრე

სეგმენტების ხის ყოველი წვერო ერთი უწყვეტი შუალედის აგრეგატს ინახავს და ნებისმიერი შუალედი O(log n) ასეთ წვეროდ იყოფა.
წერტილოვანი განახლება მხოლოდ ერთ ფოთოლსა და მის წინაპრებს ცვლის, ამიტომ ისიც O(log n) ღირს.
გამოდგება ნებისმიერი ასოციაციური ოპერაცია (ჯამი, მინიმუმი, მაქსიმუმი, უსგ): შეცვალე გაერთიანების ფუნქცია, დანარჩენი იგივე რჩება.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: მოთხოვნისას დათვალე მონიშნული წვეროები: შუალედის რიცხვებზე გაცილებით ცოტაა. განახლებისას მხოლოდ ერთი გზა ინთება ფოთლიდან სათავემდე.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

სეგმენტების ხე (ჯამი)

მასივი

52713648

სეგმენტების ხე პასუხობს შუალედის ჯამის მოთხოვნებსა და წერტილოვან განახლებებს O(log n)-ში. ყოველი კვანძი ინახავს მიმდებარე შუალედის ჯამს.

ფსევდოკოდი

 1 leaves hold the array; each internal node = sum of its two children 2 build: fill leaves, then t[v] = t[2v] + t[2v+1] bottom-up 3 query(l,r): combine O(log n) canonical nodes that tile the range 4   take a node fully inside the range; recurse otherwise 5 update(i): change the leaf, then refresh its ancestors

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

მასივზე გჭირდება შუალედის მინიმუმის მოთხოვნები, მასივი კი წერტილოვნად იცვლება. რა ჯობია?

№2

16 ელემენტზე აგებულ სეგმენტების ხეში რამდენი წვერო იცვლება ერთი ელემენტის განახლებისას?

№3

რეკურსიულ query-ში მიმდინარე წვერო ფარავს [l, r]-ს და ის მთლიანად [ql, qr]-ის შიგნითაა. რას აკეთებს?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

CSESStatic Range Sum Queries დამწყები↗LeetCodeRange Sum Query - Mutable საშუალო↗CSESDynamic Range Sum Queries საშუალო↗CSESDynamic Range Minimum Queries საშუალო↗CSESHotel Queries მოწინავე↗