ფენვიკის ხე

Август 10, 2022

Главная
Информатика
ფენვიკის ხე

Содержание

2. ფენვიკის ხე (ორობითი ინდექს-ხე): ამოცანის დასმა ვთქვათ, მოცემულია n ცალი რიცხვისაგან შედგენილი მიმდევრობა 1.) გავზარდოთ i-ური
3. ამოხსნა სტატიკური მონაცემებისათვის რაიმე B მასივში i-ურ ინდექსზე შევინახოთ 1-დან i-მდე ელემენტების ჯამი, მაშინ [l,r] ინტერვალში
4. ფენვიკის ხე: შესავალი ჩვენი მიზანია გამოვთვალოთ ელემენტთა ჯამი [1,i] ინტერვალში. გამოვიყენოთ ის ფაქტი, რომ ნებისმიერი რიცხვი
5. ფენვიკის ხე: ინტერვალები ხის წვეროებში ჩვენ ვინახავთ [i -2^r+1, i] ინტერვალში შემავალი ელემენტების ჯამს, სადაც r
6. ფენვიკის ხის სტრუქტურა f[i]=i-ური ელემენტის მნიშვნელობა c[i] = f[1] + f[2] + … + f[i] tree[i]
7. ფენვიკის ხის მაგალითი
8. ფენვიკის ხის სტრუქტურა
9. ფენვიკის ხე: შეკითხვა (Query) int read(int idx) { int sum = 0; while (idx > 0)
10. როგორ მუშაობს idx -= (idx & -idx)? idx = 44 = 1011002 -idx = 010011+1=0101002 Sum
11. ფენვიკის ხე: განახლება (Update) void update(int idx ,int val) { while (idx { tree[idx] += val;
12. როგორ მუშაობს idx += (idx & -idx)? idx = 44 = 1011002 -idx = 010011+1=0101002 tree[44]=tree[44]+val;
14. Скачать презентацию

Слайд 2

ფენვიკის ხე (ორობითი ინდექს-ხე): ამოცანის დასმა
ვთქვათ, მოცემულია n ცალი რიცხვისაგან შედგენილი

მიმდევრობა
1.) გავზარდოთ i-ური წევრის მნიშვნელობა.
2.) შეკითხვა: დავადგინოთ ელემენტთა ჯამის მნიშვნელობა [k,j] ინტერვალში

ფენვიკის ხის დადებითი მხარე:
- შეკითხვა შესრულებას უარეს შემთხვევაში სჭირდება O(log n) დრო.
- მოკლე კოდი.

Слайд 3

ამოხსნა სტატიკური მონაცემებისათვის
რაიმე B მასივში i-ურ ინდექსზე შევინახოთ 1-დან i-მდე ელემენტების

ჯამი, მაშინ [l,r] ინტერვალში მყოფი ელემენტების ჯამი ტოლი იქნება: B[r]-B[l].

Слайд 4

ფენვიკის ხე: შესავალი
ჩვენი მიზანია გამოვთვალოთ ელემენტთა ჯამი [1,i] ინტერვალში.
გამოვიყენოთ ის ფაქტი,

რომ ნებისმიერი რიცხვი შეიძლება წარმოვადგინოთ 2-ის ხარისხების ჯამით.
გამოვიყენოთ ეს თვისება [1,i] ინტერვალის წარმოსადგენად.
13 = 8 + 4 + 1
[1, 13] = [1, 8] + [9, 12] + [13, 13]

Слайд 5

ფენვიკის ხე: ინტერვალები
ხის წვეროებში ჩვენ ვინახავთ [i -2^r+1, i] ინტერვალში შემავალი

ელემენტების ჯამს, სადაც r არის ბოლო არანულოვანი ციფრის პოზიცია i-ის ორობით ჩანაწერში.
მაგალითი:
1310 = 11012, ბოლო არანულოვანი ციფრი დგას 0 პოზიციაზე.
410 = 1002, ბოლო არანულოვანი ციფრი დგას 2 პოზიციაზე.

Слайд 6