ფენვიკის ხე (ბინარული ინდექს-ხე)

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

★ ლექცია: tree_Fenwick · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 20 წთ

←ეყრდნობა

1პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარაპრეფიქს-ჯამები ინტერვალს O(1)-ში პასუხობს, მაგრამ ყოველი ცვლილების შემდეგ თავიდან უნდა დაითვალოს; ფენვიკის ხე ორივეს სწრაფს ინარჩუნებს.2ორობითი ძებნა და ძებნა პასუხზეორობითი ძებნის მსგავსად, ყოველი ბიჯი 2-ის ხარისხებით მუშაობს, ამიტომ განახლებასაც და შეკითხვასაც O(log n) სჭირდება.

გზას უხსნის→

9ბიტური ოპერაციებიფენვიკის ნახტომები idx += idx & -idx უმცროსი ერთიანი ბიტის ხერხია; ეს ეტაპი მას ზოგადად ხსნის.+სეგმენტების ხეფენვიკის ხე პრეფიქსის ჯამებს პასუხობს; სეგმენტების ხე ნებისმიერ [L, R] ინტერვალზე მინიმუმსა და მაქსიმუმსაც პოულობს, რაც ფენვიკს არ შეუძლია.

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

ისწავლე

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

01ამოცანის დასმა

მოცემულია n რიცხვისგან შედგენილი მიმდევრობა და პერიოდულად ორი სახის მოთხოვნა შემოდის (მე-2 სლაიდი):

შევცვალოთ i-ური წევრის მნიშვნელობა;
დავადგინოთ ელემენტთა ჯამი [x, y] ინტერვალში.

სტატიკური მონაცემების შემთხვევაში, როცა მასივის ელემენტები არ იცვლება, ამოცანა მარტივად იხსნება პრეფიქს-ჯამებით: prefix[i] = a[1] + … + a[i], ჯამი [x, y] ინტერვალზე კი არის prefix[y] − prefix[x − 1]. ლექციის 16 რიცხვიან მასივში ჯამი [6, 13] ინტერვალზე არის 3+1+4+2+5+2+2+3 = 22, ან ერთი გამოკლებით 33 − 11 = 22.

დინამიური მონაცემების შემთხვევაში კი a[i]-ის ყოველი ცვლილების შემდეგ i-დან n-მდე ყველა პრეფიქს-ჯამის ხელახლა დათვლა მოგვიწევს, ანუ O(n) ოპერაცია ყოველ ცვლილებაზე. ფენვიკის ხე (ბინარული ინდექს-ხე, BIT) ორივე მოთხოვნას უარეს შემთხვევაში O(log n) დროში ასრულებს, მისი კოდი კი ძალიან მოკლეა.

ლექციის 16 რიცხვი (მე-3 სლაიდი): ჯამი [6, 13] ინტერვალზე პრეფიქს-ჯამებით.

02მათემატიკური ფოკუსი: 2-ის ხარისხები

ლექცია ფოკუსით იწყება. ჩაიფიქრე რიცხვი 1-დან 60-მდე და მოძებნე ის ექვს ცხრილში: ცხრილში ა არის რიცხვები, რომელთა 2-ის ხარისხების ჯამად წარმოდგენაში 1 შედის, ცხრილში ბ ისინი, რომლებშიც 2 შედის, შემდეგ 4, 8, 16 და 32. შეკრიბე პირველი რიცხვები იმ ცხრილებიდან, რომლებშიც შენი რიცხვი მოიძებნა, და მიიღებ ჩაფიქრებულ რიცხვს.

ფოკუსი ემყარება იმ ფაქტს, რომ ნებისმიერი მთელი რიცხვი ერთადერთი გზით წარმოდგება 2-ის ხარისხების ჯამით, და ეს პირდაპირ კავშირშია რიცხვის ორობით ჩანაწერთან. 52 = 32 + 16 + 4, ანუ 52 = 110100₂, ამიტომ 52 ჩაწერილია 4-ის, 16-ის და 32-ის (გ, ე, ვ) ცხრილებში. ცხრილების იგივე კომბინაციას ვერცერთი სხვა რიცხვი ვერ მოგვცემს, რადგან ორობით სისტემაში ორ განსხვავებულ რიცხვს ერთი და იგივე ჩანაწერი ვერ ექნება.

დაიმახსოვრე ეს ფაქტი: ფენვიკის ხე იგივე ფოკუსია, ოღონდ ინტერვალებზე.

03ფენვიკის ხის იდეა

ინტერვალებიც რიცხვების მსგავსად იყოფა. 21 = 16 + 4 + 1, ამიტომ [1, 21] = [1, 16] + [17, 20] + [21, 21]; 52 = 32 + 16 + 4, ამიტომ [1, 52] = [1, 32] + [33, 48] + [49, 52]. 2-ის ხარისხების ჯამით ნებისმიერი რიცხვის წარმოდგენის ერთადერთობა ასე ინტერვალებზე გადადის.

ინფორმაციის შენახვის თვალსაზრისით ეს ნიშნავს, რომ თითოეულ ინდექსზე ვინახავთ იმდენი ელემენტის ჯამს, რამდენსაც უდრის უმცირესი წევრი ამ ინდექსის 2-ის ხარისხების ჯამად წარმოდგენისას. 21-ზე (და ზოგადად კენტ ინდექსებზე) ინახება მხოლოდ ერთი ელემენტი, 52-ზე კი 4 ელემენტის ჯამი: 49-ე, 50-ე, 51-ე და 52-ე ელემენტების. ორობით ჩანაწერში ინტერვალის სიგრძეს შეესაბამება ყველაზე მარჯვენა 1-იანი და მის მარჯვნივ მდებარე 0-ები: 12 = 1100₂ ინახავს [9, 12]-ს, 8 = 1000₂ ინახავს [1, 8]-ს, 6 = 110₂ კი [5, 6]-ს.

მასივს tree[] ვუწოდოთ; მისი ინდექსები 1-დან იწყება და სულ n უჯრაა, შესასვლელ მასივზე მეტი მეხსიერება არ გვჭირდება.

ინდექსები 1-დან 16-მდე და მათი ინტერვალები (მე-8 და მე-9 სლაიდები). მონიშნულია [1, 13]-ის სამი ინტერვალი.

04შეკითხვა და განახლება: ყველაზე მარჯვენა 1-იანი

შეკითხვა (read): [1, 52] ინტერვალის დასაფარად უნდა მივმართოთ 52-ე, 48-ე და 32-ე ინდექსებს. ორობითად 52 = 110100₂, 48 = 110000₂, 32 = 100000₂: ყოველი მომდევნო რიცხვი მიიღება წინა რიცხვიდან ყველაზე მარჯვენა 1-იანის განულებით, ვიდრე რიცხვი მთლიანად არ განულდება. ეს იგივეა, რომ რიცხვს ყოველ ჯერზე გამოვაკლოთ მისი შემადგენელი 2-ის ხარისხების ჯამიდან უმცირესი წევრი.

განახლება (update): რომელი ინტერვალების ჯამებში მონაწილეობს 37? [37, 37], [37, 38], [33, 40], [33, 48], [1, 64], [1, 128] და ყველა მომდევნო. მათ შებრუნებული პროცესით ვპოულობთ: ყოველ ჯერზე რიცხვს ვუმატებთ მისი ყველაზე მარჯვენა 1-იანის შესაბამის მნიშვნელობას, 37 → 38 → 40 → 48 → 64 → 128.

როგორ ვიპოვოთ სწრაფად მარჯვნიდან პირველი 1-იანი? კომპიუტერული არქიტექტურების უმეტესობაში გამოკლება შეკრებით არის ჩანაცვლებული: მაკლები იცვლება თავისი დამატებითი კოდით, ანუ ყველა ბიტის ინვერსიით და 1-ის დამატებით. −x-ში ყველაზე მარჯვენა 1-იანის მარცხნივ ყველა ბიტი ინვერტირებულია, თვითონ ეს ბიტი კი რჩება, ამიტომ x & -x სწორედ ამ 1-იანს გვიტოვებს. 44 = 101100₂: −44 = 010011 + 1 = 010100₂ და 101100₂ & 010100₂ = 000100₂ = 4. განახლება მიდის 44 → 48 → 64, შეკითხვა კი 44 → 40 → 32 → 0 (მე-14 სლაიდი). ორივე ციკლი მაქსიმუმ log₂n + 1-ჯერ სრულდება: O(log n).

05აგება, ჯამი [6, 13] ინტერვალზე და აგება წრფივ დროში

აგება (მე-15 სლაიდი): ვიწყებთ ნულებით სავსე tree[]-ით და ვიძახებთ update(i, a[i])-ს i = 1, 2, …, 16-ისთვის. ბიჯი პირველი: ფუნქციას მიეწოდება (1, 3) და 3 ემატება tree[1], tree[2], tree[4], tree[8] და tree[16] უჯრებს; ბიჯი მეორე: ფუნქციას მიეწოდება (2, 1) და 1 ემატება tree[2], tree[4], tree[8] და tree[16] უჯრებს; და ა.შ. საბოლოოდ ვიღებთ მე-16 სლაიდის ცხრილს: tree[] = 3 4 2 8 3 6 1 19 2 7 2 11 3 4 0 36.

ჯამი ინტერვალზე (მე-16 სლაიდი): ჯამს ორჯერ ვითვლით: სათავიდან საძებნი ინტერვალის მარჯვენა ბოლომდე და სათავიდან მარცხენა ბოლოს მეზობელ ელემენტამდე. [6, 13]-ისთვის: read(13) = tree[13] + tree[12] + tree[8] = 3 + 11 + 19 = 33, read(5) = tree[5] + tree[4] = 3 + 8 = 11, მათი სხვაობა კი 33 − 11 = 22.

აგება წრფივ დროში (მე-17 და მე-18 სლაიდები): n ცალი update O(n log n) დრო ღირს. უფრო სწრაფად: მასივი პირდაპირ დავაკოპიროთ tree[]-ში, შემდეგ i = 1-დან n-მდე ყოველი tree[i] დავუმატოთ მის უშუალო „მშობელს“ j = i + (i & −i), თუ j ≤ n. მშობელი თავის მხრივ დაგროვილ ჯამს შემდეგ საფეხურზე გადასცემს, ასე რომ ხის ყოველი წიბო მხოლოდ ერთხელ მუშავდება: O(n).

ლექცია სამი გაფართოებით მთავრდება (სლაიდები 19, 20 და 21): მინიმუმის ან მაქსიმუმის პოვნა [1..K] პრეფიქსზე (ნებისმიერ [L..R] ინტერვალზე ფენვიკის ხე ამას ვერ აკეთებს), ინვერსიათა რაოდენობის პოვნა მასივში O(N log N) დროში (მარცხნიდან მარჯვნივ გავლისას read(x) გვეუბნება, რამდენი წინა ელემენტია x-ზე არაუმეტესი, დანარჩენი წინა ელემენტები x-თან ინვერსიას ქმნის; შემდეგ update(x, 1)) და ორგანზომილებიანი ფენვიკის ხე მართკუთხედზე ელემენტთა ჯამისთვის.

ზემოთ: მე-16 სლაიდის tree[] და read(13)-ისა და read(5)-ის უჯრები. ქვემოთ: ყოველი ინდექსი თავის ჯამს მშობელს გადასცემს (მე-18 სლაიდი).

ლექციის C++ კოდიC++

update და read მე-13 სლაიდის კოდია: update val-ს უმატებს ყველა უჯრას, რომლის ინტერვალშიც idx შედის, read კი კრებს უჯრებს, რომლებიც [1, idx]-ს ფარავს. MaxVal არის n, ჯამი [l, r] ინტერვალზე კი read(r) − read(l − 1). build ფუნქცია მე-18 სლაიდიდანაა: bit[] თავიდან მასივის ასლია და ყოველი i თავის ჯამს მშობელს გადასცემს, j = i + (i & −i).

// slide 13: build and update
void update(int idx ,int val) {
    while (idx <= MaxVal) {
        tree[idx] += val;
        idx += (idx & -idx);
    }
}
// slide 13: query
int read(int idx) {
    int sum = 0;
    while (idx > 0){
        sum += tree[idx];
        idx = idx - (idx & -idx);
    }
    return sum;
}
// slide 18: build in O(n)
void build(vector<long long>& bit, int n) {
    for (int i = 1; i <= n; i++) {
        int j = i + (i & -i);
        if (j <= n) {
            bit[j] += bit[i];
        }
    }
}

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

განახლება (update)O(log n)

შეკითხვა (read)O(log n)

ჯამი [l, r] ინტერვალზე = read(r) − read(l − 1)O(log n)

აგება n ცალი update-ითO(n log n)

აგება წრფივ დროშიO(n)

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

დაიმახსოვრე

tree[i] ინახავს i-ზე დამთავრებული, i & −i სიგრძის ინტერვალის ჯამს: i-ის უმცირეს 2-ის ხარისხს.
read ყველაზე მარჯვენა 1-იანს ანულებს (idx −= idx & −idx), update კი უმატებს (idx += idx & −idx); ორივე O(log n) დროს მოითხოვს.
ინტერვალის ჯამი ორი პრეფიქს-ჯამის სხვაობაა: ჯამი [l, r] = read(r) − read(l − 1), მაგალითად [6, 13] = 33 − 11 = 22.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ლექციებიდან ასევე▶ SQRT-დეკომპოზიცია

ითამაშე

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

👀 რას უყურო: უყურე ორობით პანელს: ნარინჯისფერი რგოლი idx & −idx-ს აღნიშნავს. update მას idx-ს უმატებს, read კი აკლებს. შემდეგ შეიყვანე შენი მასივი და განახლება, მაგალითად "7 +3", და ნახე იგივე შეკითხვა ცვლილების შემდეგ.

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

ფენვიკის ხე

შეკითხვა: [6, 13]

ლექციის 16 რიცხვიანი მასივი. tree[] თავიდან ნულებითაა სავსე. აგება: ყოველი i-სთვის 1-დან 16-მდე გამოვიძახოთ update(i, a[i]), როგორც მე-15 სლაიდზე.

ფსევდოკოდი

 1 void update(int idx, int val) { 2   while (idx <= MaxVal) { 3     tree[idx] += val; 4     idx += (idx & -idx); 5   } 6 } 7 int read(int idx) { 8   int sum = 0; 9   while (idx > 0) {10     sum += tree[idx];11     idx = idx - (idx & -idx);12   }13   return sum;14 }15 sum[l, r] = read(r) - read(l - 1)

1 / 1

შეამოწმე

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

№1

რას უდრის 40 & −40?

№2

რომელ უჯრებს კრებს read(11)?

№3

რომელ ინტერვალს ფარავს tree[24]?

ივარჯიშე

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

CSESDynamic Range Sum Queries დამწყები↗CodeforcesDistinct Characters Queries საშუალო↗SPOJMatrix Summation (MATSUM) საშუალო↗CodeforcesNested Segments მოწინავე↗CodeforcesEnemy is weak მოწინავე↗