Algoritmlar va berilganlar strukturasi
Download 427.28 Kb.
|
Struktura mustaqil
Daraxt qurish
Daraxtni qurishning sodda usuli daraxt qiymatlarini 0 ga boshlash va bajarishdirn n nuqta yangilanishi,vaqt murakkabligini keltirib chiqaradiO(njurnaln) O(n log n). Shu bilan birga, muqobil yondashuv dinamik dasturlashdan foydalanib , daraxtni o'sib borayotgan indekslar bo'ylab bosqichma-bosqich yaratadi. Initializatsiya quyidagicha davom etadi: Massivni nusxalashA[n] A[n]. massivgaT[n] T[n]. daraxt qiymatlarini o'z ichiga oladi Har bir indeks uchun i 1 dan n gacha: Maylij=i+(i & (−i)) Bu kattaroq birinchi tuguni o'z ichiga oladiA[i] A[i] uning mas'uliyat doirasiga kiradi. Agarj≤n , j da tugun qiymatini yangilang:T[j]←T[j]+T[i] Ko'rsatish mumkinki, o'sha nuqtada indeksi i tsiklda erishiladi,T[i] allaqachon tugun uchun to'g'ri Fenwick qiymati i . Agari i barg tugunidir (uning mas'uliyat doirasidagi faqat bitta elementga ega) bu juda ahamiyatsiz. Agari i ichki tugun bo'lsa, tsikl o'z diapazonidagi barcha diapazon summalari bilan yangilanganligini ta'minlaydi, shuning uchun u to'g'ri Fenwick qiymatini o'z ichiga oladi. Masalan, qadamdai=4 i=4, tugun 4 (boshlang'ich qiymati bilanA[4] A[4]) tomonidan oshirilgan bo'ladiT[2] T[2](bu summani o'z ichiga oladiA[1]+A[2] A[1]+A[2]) vaT[3] T[3](qiymatni o'z ichiga oladiA[3] A[3]) va shuning uchun diapazon summasini o'z ichiga oladiA(0,4] A(0,4] daraxtning dastlabki 4 elementidan. Har bir yangilanish indeks uchun ko'pi bilan bir marta sodir bo'lganligi sababli, natijada algoritm shunday bo'ladiO(n) O(n) vaqt murakkabligi. Bu, shuningdek, nusxa ko'chirish va qo'shimcha saqlashni yo'qotib, asl qatorda amalga oshirilishi mumkinT[n] T(n). Fenvik daraxtini dastlabki chastotalar qatoriga aylantirish uchun shunga o'xshash operatsiyani bajarish mumkinA[n] A[n], n dan 1 gacha teskari takrorlash va qiymatini ayirish orqalij=i+(i & (−i)) qiymatidani i har bir vaqt oralig'ida. Kamroq samaraliO(n) O(n). Daraxtni qurish algoritmi ikki bosqichda ishlaydi: birinchi o'zgartirishA[n] A[n] prefiks summasiga (qabul qiladiO(n) O(n) vaqt), keyin n..1 dan teskari takrorlash, prefiks summalarining farqini hisoblash orqali har bir tugun diapazoni yig'indisini hisoblang:SA(parent(i),i]=SA(0,i]−SA(0,parent(i)] . [5] C# da amaliy bo’lim. using System; namespace Fenvik_daraxtlar { class FenwickTree0 { private int[] data; private int getParent(int i) { return i - (i & (-i)); } private int getNext(int i) { return i + (i & (-i)); } public FenwickTree0(int n) { data = new int[n + 1]; } public int GetSum(int i) { int sum = 0; ++i; while (i > 0) { sum += data[i]; i = getParent(i); } return sum; } public void Update(int i, int v) { ++i; while (i < data.Length) { data[i] += v; i = getNext(i); } } } class FenwickTree { private int[] A; private int SIZE; public FenwickTree(int size) { SIZE = size; A = new int[SIZE]; } private int LSB(int i) { return i & -i; } public int PrefixSum(int i) { int sum = A[0]; for (; i != 0; i -= LSB(i)) sum += A[i]; return sum; } public void Add(int i, int delta) { if (i == 0) { A[0] += delta; return; } for (; i < SIZE; i += LSB(i)) A[i] += delta; } }
class Program { static int SIZE = 10; static int[] A = new int[SIZE]; static int LSB(int x) { return x & -x; } static int range_sum(int i, int j) { int sum = 0; for (; j > i; j -= LSB(j)) sum += A[j]; for (; i > j; i -= LSB(i)) sum -= A[i]; return sum; } static void init() { for (int i = 1; i < SIZE; ++i) { int j = i + LSB(i); if (j < SIZE) A[j] += A[i]; } } static void fini() { for (int i = SIZE - 1; i > 0; --i) { int j = i + LSB(i); if (j < SIZE) A[j] -= A[i]; } } static int get(int i) { return range_sum(i, i + 1); } static void set(int i, int value) { add(i, value - get(i)); } static uint rank_query(int value) { int i = 0, j = SIZE - 1; value -= A[0]; for (; j > 0; j >>= 1) { if (i + j < SIZE && A[i + j] <= value) { value -= A[i + j]; i += j; } } return (uint)i; } static void add(int i, int value) { for (; i < SIZE; i += LSB(i)) A[i] += value; } static void Main(string[] args) { //// bu qism classni chaqirib ishlatishga kerak //int[] A = { 5, 8, 1, 2, 6, 9, 7, 3, 4, 0 }; //FenwickTree tree = new FenwickTree(A.Length); //for (int i = 0; i < A.Length; i++) // tree.Add(i, A[i]); //Console.WriteLine(tree.PrefixSum(5)); ///bu qismi alohida metodlariga kerak // A massivini boshlash init(); // 0-dan boshlab 5 ta qiymatni A massiviga qo'shish A[0] += 1; A[1] += 2; A[2] += 3; A[3] += 4; A[4] += 5; // A massivning 2-chi elementini 10 ga o'zgartirish set(2, 10); // A massivning 3-dan 5-gacha bo'lgan elementlarining yig'indisini hisoblash int sum = range_sum(3, 6); // 4 ta elementga teng yoki kichik qiymatga ega elementlar sonini topish uint count = rank_query(4); // A massivni tugatish fini(); Console.WriteLine($"Sum: {sum}"); Console.WriteLine($"Count: {count}"); }
Fenwick Tree (Binary Indexed Tree) adli datalar strukturasi yaratilgan. Fenwick Tree, massiv elementlarining qiymatlarini qo'shish va ularning yig'indilarni hisoblash uchun mo'ljallangan. Bu klassda ikki xil funksiya mavjud: PrefixSum(i) - berilgan indeks gacha massiv elementlarining yig'indisini hisoblaydi; Add(i, delta) - berilgan indeksdagi massiv elementiga delta qiymatini qo'shib qo'yadi. Klass obyekti yaratilishida, size o'zgaruvchisi beriladi va Fenwick Tree massivi yaratiladi. PrefixSum funksiyasi berilgan indeks bo'yicha massiv elementlarining yig'indisini hisoblaydi. Add funksiyasi berilgan indeksdagi massiv elementga delta qiymatini qo'shib qo'yadi. LSB funksiyasi, berilgan sonning eng kichik turdagi bitini qaytaradi. Bu funksiya Fenwick Tree ni hisoblashda ishlatiladi. Bu koddagi FenwickTree0 sinfi, data nomli int tipidagi massivdan iborat. getParent() va getNext() metodlari esa, mos sonning ota-ona elementlari (parent va next) indeksini topish uchun ishlatiladi. Sinfdagi GetSum() metodi data massivining 0-chi elementidan boshlab, i-chi elementiga qadar bo'lgan elementlarning yig'indisini hisoblaydi. Update() metodi esa, i-chi elementni v qiymati bilan yangilaydi. Bu metoddan oldin i-ni 1 taga oshiriladi, chunki massiv 0-dan boshlanadi. Quyidagi metodlar mavjud: int[] A massivi va SIZE o'zgaruvchisi ma'lum bir amaldagi masalaning hisob-kitob qilish uchun berilgan. init() funksiyasi A massivini boshlash va fini() funksiyasi A massivini tugatish uchun ishlatiladi. range_sum(i, j) funksiyasi A massivning i dan j gacha bo'lgan elementlarining yig'indisini hisoblash uchun ishlatiladi. set(i, value) funksiyasi A massivning i-chi elementini value ga o'zgartirish uchun ishlatiladi. get(i) funksiyasi A massivning i-chi elementini qaytaradi. rank_query(value) funksiyasi A massivida qiymati value ga teng yoki undan kichik elementlar sonini topish uchun ishlatiladi. Download 427.28 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling