პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარა

მასივის ბევრი ამოცანა შუალედებს ეხება: მონაკვეთის ჯამი, უმოკლესი მონაკვეთი, რომელიც მიზანს აღწევს, წყვილი, რომლის ჯამიც საჭიროა. სამი პატარა ხრიკი ამათ O(n²)-დან O(n)-ად აქცევს.

საშუალო⏱ 14 წთ

←ეყრდნობა

1მასივები და დინამიური მასივებიპრეფიქსული ჯამები მეორე მასივია, სადაც ნებისმიერი შუალედის ჯამი ორი O(1) წვდომაა.0სირთულე და ზრდის ტემპიორივე ხერხი O(n²) ჩადგმულ ციკლებს ერთ O(n) გავლად აქცევს.1ჰეშ-ცხრილები: set და mapმოცემული ჯამის მქონე ქვემასივების დასათვლელად უკვე ნანახ პრეფიქსულ ჯამებს ჰეშ-ცხრილში ვინახავთ.

გზას უხსნის→

2სწრაფი სორტირება და დაყოფადაყოფა არის ორი მაჩვენებელი, რომლებიც ერთმანეთისკენ მოძრაობენ და არასწორ ადგილას მდგომ ელემენტებს ცვლიან.2დათვლითი სორტირებამთვლელების პრეფიქსული ჯამები თითოეულ გასაღებს ეუბნება, სად იწყება მისი ბლოკი პასუხში.5ფენვიკის ხე (ბინარული ინდექს-ხე)პრეფიქს-ჯამები ინტერვალს O(1)-ში პასუხობს, მაგრამ ყოველი ცვლილების შემდეგ თავიდან უნდა დაითვალოს; ფენვიკის ხე ორივეს სწრაფს ინარჩუნებს.11გულუბრყვილო შაბლონის ძებნაგულუბრყვილო ძებნა m სიგრძის ფანჯარას ტექსტზე აცურებს.+Z-ფუნქციაის უმარჯვენესი დამთხვევის [l, r] ფანჯარას ინახავს, რომ უკვე გაკეთებული შედარებები გამოტოვოს.

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

ისწავლე

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

01პრეფიქსული ჯამები: ერთხელ გამოთვალე, მყისიერად უპასუხე

a[l..r]-ის ციკლით შეჯამება ყოველ კითხვაზე O(n) ღირს. მილიონი კითხვისთვის ეს ზედმეტად ნელია.

სანაცვლოდ ერთხელ ააგე პრეფიქსული ჯამები: p[0] = 0 და p[i+1] = p[i] + a[i]. ესე იგი p[i] პირველი i ელემენტის ჯამია.

ახლა ნებისმიერი შუალედის ჯამი ერთი გამოკლებაა:

sum(a[l..r]) = p[r+1] − p[l]

p[r+1] ყველაფერს მოიცავს r-მდე, p[l] კი l-მდე ნაწილს აკლებს. სურათზე: a[2..5] = p[6] − p[2] = 23 − 4 = 19.

აგება O(n)-ია, ყოველი კითხვა O(1). ფრთხილად ერთით აცდენასთან: p-ს n+1 ელემენტი აქვს და p[i] ნიშნავს „i ინდექსამდე“.

02ორი მაჩვენებელი დალაგებულ მასივზე

იპოვე დალაგებულ მასივში ორი რიცხვი, რომელთა ჯამი მიზანს უდრის. ყველა წყვილის შემოწმება O(n²)-ია. სანაცვლოდ დასვი მაჩვენებელი L დასაწყისში და R ბოლოში:

თუ a[L] + a[R] მცირეა, მისი გაზრდის ერთადერთი გზა L-ის მარჯვნივ წაწევაა
თუ დიდია, R-ს მარცხნივ წავწევთ
თუ ტოლია, მზადაა

ყოველი ბიჯი ერთ ელემენტს სამუდამოდ გამორიცხავს. რატომაა ეს უსაფრთხო? თუ ჯამი დიდია, a[R] დარჩენილთაგან უმცირეს პარტნიორთანაც დიდია, ამიტომ a[R] პასუხის ნაწილი ვერასდროს იქნება.

მაჩვენებლები მხოლოდ ერთმანეთისკენ მოძრაობს, ამიტომ გავლა მაქსიმუმ n ბიჯია: O(n). იგივე ნიმუში აერთებს ორ დალაგებულ სიას და დუბლიკატებს ადგილზე შლის.

03მოცურავი ფანჯარა

მოცურავი ფანჯარა არის ერთი მიმართულებით მოძრავი ორი მაჩვენებელი, l და r, რომლებიც უწყვეტ მონაკვეთს a[l..r]-ს აღნიშნავს. შეინახე მიმდინარე მნიშვნელობა (მაგ. ჯამი) და განაახლე, როცა კიდეები მოძრაობს:

გაფართოება: r წაწიე მარჯვნივ და დაუმატე a[r]
შეკუმშვა: სანამ ფანჯარა „ზედმეტია“ (ჯამი ≥ მიზანი), ჩაიწერე პასუხი და l წაწიე მარჯვნივ, გამოაკელი a[l]

ასე პოულობ, მაგალითად, უმოკლეს ქვემასივს ჯამით ≥ S, ან ყველაზე გრძელ ქვესტრიქონს განმეორებადი სიმბოლოების გარეშე (ფანჯრის მდგომარეობად სიმრავლით ან მთვლელებით).

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

04როდის რომელი ხრიკი მუშაობს

ამ ხრიკებს კონკრეტული სტრუქტურა სჭირდება, ამიტომ ჯერ ის შეამოწმე:

პრეფიქსულ ჯამებს შექცევადი ოპერაცია სჭირდება: ჯამი (გამოკლება), XOR (ისევ XOR), დათვლა. შუალედის მინიმუმისა და მაქსიმუმისთვის არ მუშაობს. ასევე სტატიკური მასივი სჭირდება: თუ მნიშვნელობები კითხვებს შორის იცვლება, ფენვიკის ან სეგმენტების ხე გჭირდება.
ორ მაჩვენებელს ორი ბოლოდან დალაგებული მონაცემი სჭირდება, რომ გადაწყვეტილება „მცირე / დიდი“ სწორი იყოს.
მოცურავ ფანჯარას მონოტონურობა სჭირდება: ფანჯრის გაზრდამ ჯამი მხოლოდ უნდა გაზარდოს. უარყოფით რიცხვებთან ეს ირღვევა. მაშინ გამოიყენე პრეფიქსული ჯამები და ჰეშ-ასახვა: ჯამით k ქვემასივები დათვალე, თუ ადრინდელ პრეფიქსებში p[r+1] − k-ს მოძებნი.

სასარგებლო ნიშანი: პირობაში „ქვემასივი“, „ქვესტრიქონი“ ან „წყვილი“ და n 10⁵ ან მეტი.

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

პრეფიქსული ჯამების აგებაO(n)

შუალედის ჯამის კითხვაO(1)

ორი მაჩვენებელი (წყვილი)O(n)

მოცურავი ფანჯარაO(n)

დაიმახსოვრე

p[i+1] = p[i] + a[i]-ით ნებისმიერი შუალედის ჯამი არის p[r+1] − p[l], O(1)-ში.
ორი მაჩვენებელი იმიტომ მუშაობს, რომ ყოველი სვლა ერთ ელემენტს უსაფრთხოდ და სამუდამოდ გამორიცხავს.
მოცურავი ფანჯარა O(n)-ია, რადგან l და r მხოლოდ წინ მოძრაობს, მაგრამ არაუარყოფით მნიშვნელობებს მოითხოვს.

ითამაშე

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

👀 რას უყურო: ჯერ უყურე, როგორ ივსება prefix[] მარცხნიდან მარჯვნივ, მერე ნახე, რომ შუალედის ყოველი კითხვა მხოლოდ ორ უჯრას იყენებს. ფანჯრის ფაზაში შენიშნე, რომ l უკან არასდროს მიდის.

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

პრეფიქსული ჯამები და ორი მიმთითებელი

i	0	1	2	3	4	5	6	7	8
a[]		3	1	4	1	5	9	2	6
prefix[]	0	·	·	·	·	·	·	·	·

პრეფიქსული ჯამები წინასწარ ითვლის დაგროვილ ჯამებს, ასე რომ ნებისმიერი შუალედის ჯამი ერთ გამოკლებად იქცევა.

ფსევდოკოდი

 1 prefix[0] = 0 2 prefix[i+1] = prefix[i] + a[i]        // O(n) once 3 sum(l..r) = prefix[r+1] - prefix[l]   // O(1) each 4 // two pointers: shortest window with sum >= target 5 expand r, adding a[r] to the window sum 6 while sum >= target: record length, shrink from l

1 / 1

შეამოწმე

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

№1

a = [2, 5, 1, 4]. პრეფიქსული მასივია p = [0, 2, 7, 8, 12]. რას უდრის sum(a[1..3])?

№2

დალაგებული მასივი [1, 4, 6, 9, 12], მიზანი 15. L მიუთითებს 1-ზე, R 12-ზე (ჯამი 13). რა ხდება შემდეგ?

№3

დათვალე ქვემასივები ზუსტად k ჯამით, როცა მასივში უარყოფითი რიცხვებიცაა. რომელი მიდგომაა სწორი?

ივარჯიშე

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

CSESStatic Range Sum Queries დამწყები↗LeetCodeTwo Sum II - Input Array Is Sorted საშუალო↗LeetCodeMinimum Size Subarray Sum საშუალო↗CSESSubarray Sums I საშუალო↗LeetCodeSubarray Sum Equals K საშუალო↗