Fenvik daraxti va algoritmi
![FENVIK DARAXTI VA ALGORITMI
2.1 Fenvik daraxti haqida umumiy tushuncha
Fenvik daraxti dasturlashda o‘zining o‘ziga xos xususiyatlari bilan
ajratilgan. Bu xususiyatlar esa o‘zgaruvchan va o‘zgarmas bo‘lishi mumkin.
Fenvik daraxti (ingliz tilidan olingan bo‘lib, “ikkilik indeksli daraxt” degan
ma’noni anglatadi) – prefiks yig‘indisini samarali hisoblashi va elementlarni
yangilashi mumkin bo‘lgan ma’lumotlar tuzilishi, saqlashni talab qiladigan
ma’lumotlar tuzilishi O(n) o‘lchovli xotira va samarali hisoblangan quyidagi
operatsiyalarni bajarish kabi bir qancha vazifalarni bajaradi:
qatordagi istalgan elementning qiymatini osongina o‘zgartirish;
[i, j] segmentdagi assotsiativ, komutativ, qiymat qaytaradigan operatsiyani
bajarish(odatda bu yig‘indini hisoblovchi yig‘indi funksiyasi);
Ikkilik daraxtning barglarida asl massivning qiymatlari, qolgan tugunlarida
esa avlodlarning qiymatlari yig‘indisi saqlanadi. Fenvik daraxti yordamida har bir
butun sonni ikki daraja yig‘indisi sifatida ifodalash mumkin. Xuddi shu tarzda,
jami yig‘indini ushbu o‘zgaruvchan chastota to‘plamlari yig‘indisi sifatida
hisoblash mumkin.
Fenvik daraxtining strukturasi hamda unda yig‘indi funksiyasining
qo‘llanilishi quyidagicha:
vector<int> daraxt;
int size;
void increase(int index, int value)
{
for(int i=index; i<size; i = (i | (i+1)))
daraxt[i] += value;
}
int sum(int right)
5](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_5.png)
![{
int result = 0;
for(int j = right; j>=0; j = (j&(j+1)) – 1)
result += daraxt[j];
return result;
}
Bu dasturda Fenvik daraxt(binary indexed tree, ikkilik indeksli daraxt)
nomli ma’lumotlar strukturasini ishlatilgan. Bu struktura massivdagi
elementlarning qiymatlarini saqlash uchun ishlatiladi va massivdagi
elementlarning qiymatlarini o‘zgartirish va ularning yig‘indisini hisoblash uchun
ham yaxshi natijalar beradi.
Dasturda daraxt nomli vector<int> e’lon qilingan, bu esa Fenvik daraxtni
saqlash uchun ishlatiladi. size esa massivning o‘lchamini ifodalaydi.
increase funksiyasi massivdagi bir elementning qiymatini o‘zgartirish
uchun ishlatiladi. Uning ikkita argumenti bor: index va value . index massivdagi
o‘zgartiriladigan elementning indeksini, value esa o‘zgartiriladigan qiymatni
ifodalaydi. Funksiya for sikli yordamida Fenvik daraxtini yangilaydi.
sum funksiyasi esa massivdagi bir nechta elementlarning yig‘indisini
hisoblash uchun ishlatiladi. Uning argumenti right massivdagi oxirgi elementning
indeksini ifodalaydi. Funksiya for sikli yordamida Fenvik daraxtini orqaga
yo‘naltirib, yig‘indini hisoblaydi va natijani qaytaradi.
Fenvik daraxti amalga oshirish oson, tez ishlaydi, lekin nazariy jihatdan
mutlaqo aniq bo‘lmagan ma’lumotlar tuzilishi hisoblanadi. Xuddi shu
murakkablikka qaramay, Fenvik daraxti segmentlar daraxtiga qaraganda ancha
tezroq ishlaydi. Murakkabligi O(logn) bo‘lishiga qaramay, Fenvik daraxti
segmentlar daraxtiga qaraganda ancha tezroq ishlaydi. Fenvik daraxti qo‘llanilishi
esa, dasturchilar tomonidan o‘zgaruvchan ma’lumotlar saqlash uchun ishlatiladi.
6](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_6.png)
![ishlaydigan, mavjud bo‘lgan minimal xotira miqdorini egallaydigan ma’lumotlar
tuzilishi tez hamda tartibli yoziladigan va katta miqdordagi ma’lumotlar osonroq
umumlashtiriladigan daraxt turi hisoblanadi. Ushbu struktura segmentlar
daraxtiga o‘xshaydi, ammo ushbu daraxt ma’lumotlar tuzilmasini tuzishni amalga
oshirish ancha oson hamda soddaroq. Fenvik daraxti ma’lumotlar tuzilishi
massivdagi daraxt bo‘lib, u quyidagi xususiyatlarga ega:
• har qanday [L; R] segmentidagi ba’zi qaytariladigan F operatsiyasining
qiymatini logarifmik vaqt ichida hisoblash imkonini beradi;
• har qanday elementning qiymatini O(logn)ga o‘zgartirishga imkon beradi;
• O(n) qiymatdagi xotirani talab qiladi;
F operatsiyasini turli yo‘llar bilan tanlash mumkin, lekin ko‘pincha interval
yig‘indisi operatsiyalari, interval mahsuloti, shuningdek ma’lum bir modifikatsiya
va cheklovlar, intervalda maksimal va minimalni topish yoki boshqa operatsiyalar
olinadi. A sosiylaridan biri shundaki, asl massivning bitta elementini
o‘zgartirganda, o‘rtacha O(n) qisman yig‘indilarni qayta hisoblash kerak va bu
vaqt talab etadi. Ushbu muammoni hal qilish uchun siz Fenvik daraxtidan
foydalanishingiz mumkin. Fenvik daraxlarining asosiy afzalligi uni tuzishning
osonligi va ma’lumot izlash so‘rovlarga javoblarning tezligi O(1)ga teng
bo‘lganligidadir.
9](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_9.png)
![2.2 Fenvik daraxtining amaliyotda qo‘llanilishiga oid
algoritmlar
2.2.1 Quyida Fenvik daraxtining ushbu vazifa uchun qo‘llash
Tabiiy sonlarda aniqlangan va x&(x+1) (&- bit va) ga teng bo‘lgan g (x)
funksiyasini kiritamiz. Shunday qilib, g(x) = x, agar x ning ikkilik kengayishida
oxirgi 0 bo‘lsa (x/2). Va agar ikkilik kengayishda x kichik raqamlarda birliklar
guruhi mavjud bo‘lsa, unda funksiya x ga teng bo‘lib, oxirgi birliklar 0 ga
almashtiriladi.
Massiv berilsin A =[ a 0 , a 1 ,..., an − 1 ] . Biz massivni Fenvik daraxti deb ataymiz.
T daraxtdan n ta elementlar: T[i] =∑
k = F ( i ) i
ak , qayerda i = 0 .. n − 1 .. va F [ i ] - daraxt
ustida ishlash vaqtini tanlashga bog‘liq bo‘lgan ba’zi funktsiyalar. Vaqt o‘tishi
bilan elementni kiritish va o‘zgartirish operatsiyalarini bajarishga imkon
beradigan funktsiyalar mavjuddir. Murakkabligi - O ( logn ) ga teng. U oddiy
formula bilan berilgan: F [ i ]= i& ( i + 1 ) , qayerda & -bu bit mantiqiy operatsiya AND .
Qachon AND raqamlar va uning qiymatlari bittaga ko‘paytirilsa, biz bu raqamni
ketma-ket so‘nggi birliklarsiz olamiz.
Ushbu funksiyani boshqa formula bo‘yicha hisoblash mumkin:
F(i) = i – 2 h(i)
+1 , qayerda h(i) - raqamning ikkilik yozuvining oxirida ketma-
ket keladigan birliklar soni i . Ikkala variant ham tengdir, chunki ushbu
formulalardan biri tomonidan berilgan funktsiya raqam oxirida ketma-ket
keladigan barcha birliklarni nol bilan almashtiradi.
Dasturdagi ushbu funksiya kodi quyidagicha:
10](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_10.png)
![const int N=100;
int t[N],a[N];
int sum(int L, int R)
{
int res=0;
while (R >= 0) {
res += t[R];
R = G( R ) - 1;
}
while (L >= 0) {
res -= t[L];
L = G(L) - 1;
}
return res;
}
Shuni ham ta’kidlash kerakki, har bir dastur uchun g (x) funksiyasi x ikkilik
yozuvidagi birliklar sonini kamida 1 ga kamaytiradi. Shundan kelib chiqadiki,
yig‘indini hisoblash O(log n) uchun amalga oshiriladi.
Elementlarni almashtirish quyidagicha:
Elementlarning qanday o‘zgarishiga qarab qisman yig‘indilarni tezda
o‘zgartirishni o‘rganishimiz kerak. Keyin biz massiv elementlarini o‘zgartirishimiz
kerak T[j], bunda ushbu tengsizlik o‘rinli bo‘ladi - G(j)<k<j. Barcha kerakli j lar
k[i] ketma-ketligiga tegishli bo‘ladi:
11](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_11.png)
![Bu yerda bit tushuniladi:
Shuni ta’kidlash kerakki, bu funksiya qat’iy ravishda o‘sib boradi va eng
yomon holatda O(log) marta qo‘llaniladi, chunki u har safar k sonining ikkilik
kengayishida bitta birlikni qo‘shadi.
A[k] elementini d ga o‘zgartiradigan va shu bilan birga tegishli qisman
yig‘indilarni o‘zgartiradigan funksiyani yozamiz.
Dasturdagi ushbu funksiya kodi quyidagicha:
const int N=100;
int t[N],a[N];
void upd(int k, int d)
{
a[k]+=d;
while(k<N)
{
t[k]+=d;
k=(k|(k+1));
}
}
Bu Fenvik daraxtini berilgan qiymat bilan yangilaydigan C++ funksiyasi.
12](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_12.png)
![Funksiya kirish sifatida ikkita butun sonni oladi, k va d, ular mos ravishda
yangilanadigan elementning indeksini va elementga qo‘shiladigan qiymatni
ifodalaydi. Funksiya avval a massividagi elementning qiymatini unga D qo‘shib
yangilaydi. Keyin Fenvik daraxtidagi tegishli tugunlarni vaqt sikli yordamida
daraxt ustida takrorlash orqali yangilaydi. Sikl k indeksidan boshlanadi va daraxt
bo‘ylab ildizga ko‘tariladi va yo‘l davomida har bir tugunni yangilaydi. Yangilash
qo‘shish orqali amalga oshiriladi d indeksdagi tugun qiymatiga k va keyin formula
yordamida ota tugunga o‘tish: k = (k | (k + 1)).
| operatorining ikkilik qismlarini birlashtirgan k|(k + 1) operatsiyasi eng
o‘ngdagi 0 bitni aylantiradi k 1 ga va | operatsiyasi natijada olingan ikkilik
raqamlarni birlashtiradi. Ushbu formula daraxtni berilgan indeksdan uning asosiy
indeksiga ko‘tarish uchun ishlatiladi.
Umuman olganda, ushbu funktsiya Fenvik daraxtini berilgan qiymat bilan
yangilash uchun ishlatiladi, bu raqamlar qatorida samarali so‘rovlar va
yangilanishlarni amalga oshirishga imkon beradi.
t[i] - barcha f(i) uchun a[j] yig‘indisi < = j < = i bo‘lgan holat.
sum funktsiyasi - a qatorining barcha elementlari bo‘ylab harakatlanadigan joyga t
qatori bo‘ylab harakatlanib, iloji boricha segmentlar bo‘ylab "sakrash" ni amalga
oshiradi.
Upd funktsiyasi teskari yo‘nalishda - indekslarni ko‘paytirish tomon siljiydi, t[j]
yig‘indisi qiymatlarini faqat kerakli pozitsiyalar uchun yangilaydi, ya’ni
f (j) <= i <= j bo‘lgan barcha j uchun. Shubhasiz , ikkala operatsiyaning tezligi F
funksiyasini tanlashga bog‘liq bo‘ladi.
Ishga tushurishda endi biz t qatorini dastlabki hisoblashda uni nol bilan
boshlash mumkinligini ta’kidlaymiz. Shundan so‘ng, biz n ta elementning har biri
uchun upd(i, a[i]) funksiyasidan foydalanamiz. Keyin dastlabki hisoblash O(n*log
n)ga teng vaqtni oladi, bu oddiy qismiy yig‘indilar bilan tavsiflangan algoritmga
qaraganda ko‘proq vaqtni oladi.
13](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_13.png)
![2.2.2 Fenvik daraxti yordamida diapazon yig‘indisini hisoblash uchun
dastur kodi
1-qadam: Prefiks yig‘indisi daraxtini yangilash.
void update(int ind,int num){
while(ind<v.size()){
v[ind]+=num;
ind+=(ind & -ind);
}
}
2-qadam: Prefiks yig‘indisi daraxtiga so‘rovlar.
int getsum(int ind)
{
int sum=0;
while(ind>0)
{
sum+=v[ind];
ind-=(ind & -ind);
}
return sum;
}
3-qadam: Daraxt qurish .
for(int i=0;i<n;i++)
{
int num;
15](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_15.png)
![cin>>num;
update(i+1,num);
}
4-qadam: Diapazon miqdorini olish .
while(t--)
{
int l,r;
cin>>l>>r;
cout<<getsum(r)-getsum(l-1)<<endl;
}
Ikkilik indekslangan daraxtni amalga oshirish oson va chiziqli xotirani
egallaydi. So‘rov va yangilash jarayoni O(log n ) vaqtini oladi.
Fenvik daraxti yordamida prefikslarda past/yuqori darajalarni saqlash ham
mumkin, ammo bunday daraxtning qo‘llab-quvvatlanadigan operatsiyalar sezilarli
darajada cheklangan:
• prefiksdagi minimal / maksimal qiymatlarga ko‘ra, o‘zboshimchalik
segmentida qiymatni belgilash mumkin emas.
• faqat elementlarni kamaytirish (minimal qidirish uchun
daraxt)/kattalashtirish (maksimal qidirish uchun daraxt) mumkin.
Amalga oshirish yig‘indini topish uchun amalga oshirish bilan deyarli bir xil:
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000]; //Massiv e’loni
16](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_16.png)
![int f[100000]; //Fenvik daraxti
int get_min(int x) {
int result = INT_MAX;
for (; x >= 0; x = (x & (x + 1)) - 1) {
result = min(result, f[x]);
}
return result;
}
void assign(int idx, int val) {
a[idx] = val;
for(; idx < n; idx |= idx + 1) {
f[idx] = min(f[idx], val);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++){
f[i] = INT_MAX;
}
for (int i = 0; i < n; i++){
int t;
cin >> t;
assign(i, t);
}
return 0;
}
Bu Fenvik daraxti ma’lumotlar tuzilishini amalga oshiradigan C++ dasturi.
Fenvik daraxti, shuningdek, ikkilik indekslangan daraxt sifatida ham tanilgan, bu
17](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_17.png)
![2.2.3 Fenvik daraxti yordamida eng katta ketma-ketlik muammosini
maksimal darajada hal qilish vazifasi
Yechish uchun ketma-ketlik elementlarini cheklash muhimdir. Agar a
i<= 10 6
,
keyin muammoni Fenvik daraxti yordamida hal qilish mumkin, aks holda avval
qiymatlarni "siqish" kerak.
Yechim g‘oyasi juda oddiy: qatorni qo‘llab-quvvatlab, chapdan o‘ngga
ketma-ket boramiz. Keyingi elementni qayta ishlashda biz u bilan tugaydigan
ketma-ketlikning uzunligini yaxshilashga harakat qilamiz. Buning uchun biz har
qanday qisqa uzunlikdagi ketma-ketlikni davom ettirishimiz yoki yangisini
boshlashimiz mumkin. Formula sifatida buni quyidagicha yozish mumkin (joriy
element x):
f[x]=max(f[x],maxi=0x−1f[i]+1)
Formulada maksimal prefiksga e’tibor bering. Agar siz uni Fenvik daraxti
bilan topsangiz murakkablik O(logn), muammoni hal qilish uchun murakkablik
O(nlogn)ga teng bo‘ladi. Formulada maksimal prefiksga e’tibor bering. Agar siz
uni Fenvik daraxti bilan topsangiz murakkablik O(logn), muammoni hal qilish
uchun murakkablik O(nlogn)ga teng bo‘ladi.
C++da amalga oshirish:
#include <bits/stdc++.h>
using namespace std;
int n;
int seq[100000];
int a[1000001];
int f[1000001];
int get_max(int x) {
int result = INT_MIN;
19](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_19.png)
![for (; x >= 0; x = (x & (x + 1)) - 1) {
result = max(result, f[x]);
}
return result;
}
void assign(int idx, int val) {
a[idx] = val;
for(; idx <= 1000000; idx |= idx + 1) {
f[idx] = max(f[idx], val);
}
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> seq[i];
}
for(int i = 0; i < n; i++) {
int x = seq[i];
int prev_max = get_max(x - 1);
if (prev_max + 1 > a[x]) {
assign(x, prev_max + 1);
}
}
int ans = get_max(1000000);
cout << ans << endl;
}
20](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_20.png)
Fenvik daraxti va algoritmi 1. MUNDARIJA I. KIRISH ....................................................................................... 2 II. FENVIK DARAXTI VA ALGORITMI ................................................ 5 2.1 Fenvik daraxti haqida umumiy tushuncha ........................................................ 5 2.2 Fenvik daraxtining amaliyotda qo‘llanilishiga oid algoritmlar ...................... 10 2.2.1 Quyida Fenvik daraxtining ushbu vazifa uchun qo‘llash ........................................................... 10 2.2.2 Fenvik daraxti yordamida diapazon yig‘indisini hisoblash uchun dastur kodi ........................... 15 2.2.3 Fenvik daraxti yordamida eng katta ketma-ketlik muammosini maksimal darajada hal qilish vazifasi ............................................................................................................................................... 19 2.3 Fenvik daraxt strukturasini yaratish bo‘yicha umumiy ko‘rsatmalar ............ 22 III. XULOSA ................................................................................... 23 IV. FOYDALANILGAN ADABIYOTLAR: ............................................. 26 4.1 Ijtimoiy sahifalar va saytlarda mavjud adabiyotlar: ...................................... 26 1
KIRISH Dasturlashda daraxtlar kodni tuzishda bo‘lgan muammolar va xatolar yuzasidan yordam olish uchun ishlatiladi. Daraxtlar muhim funksiyalar va o‘zaro bog‘lanishni ta’minlash uchun yaratilgan hamda dastur kodi oson yozilishi uchun ishlatiladi. Hisoblashda ishlatiladigan daraxtlar grafik nazariyasidagi daraxtlarning matematik konstruksiyalariga o‘xshash, ammo farq qilishi mumkin, to‘plamlar nazariyasidagi daraxtlar va tavsiflovchi to‘plamlar nazariyasidagi daraxtlar. Daraxt ma’lumotlar tuzilishi - bu ma’lumotlarni joylashtirish va qidirish oson bo‘lgan tarzda ifodalash, hamda tartibga solish uchun ishlatiladigan ierarxik tuzilma. Bu qirralar bilan bog‘langan va tugunlar o‘rtasida ierarxik munosabatlarga ega bo‘lgan tugunlar to‘plamidir. Daraxtning eng yuqori tuguniga ildiz, uning ostidagi tugunlarga esa avlod tugunlari deyiladi. Ushbu ma’lumotlar tuzilishi kompyuterda ma’lumotlarni yanada samarali ishlatish uchun tartibga solish va saqlashning maxsus usuli hisoblanadi. U qirralar orqali bog‘langan markaziy tugun, strukturaviy tugunlar va pastki tugunlardan iborat. Shuni ham aytishimiz mumkinki, daraxt ma’lumotlari tuzilishi bir-biri bilan bog‘langan ildizlar, novdalar va barglarga ega. Har bir tugunda bir nechta avlod tugunlar bo‘lishi mumkin va bu avlod tugunlari ham o‘zlarining avlod tugunlariga ega bo‘lib, rekursiv tuzilmani hosil qiladi. Daraxtlar - bu dinamik to‘plam amallarni bajaradigan ma’lumotlar tuzilmalari. Bunday amallar sifatida elementni qidirish, minimal(maksimal) elementni qidirish, kiritish, o‘chirish, avlod-ajdodga o‘tish, avlodga o‘tish kabilarni keltirish mumkin. Shunday qilib, daraxt oddiy lug‘at sifatida ham, ustivor navbat sifatida ham ishlatilishi mumkin. Daraxtdagi ma’lumotlar ketma-ket saqlanmaydi, ya’ni ular chiziqli saqlanmaydi, balki ular bir necha darajalarda joylashtirilgan va biz buni iyerarxik tuzilma deb aytishimiz mumkin. Shu sababli, daraxt chiziqli bo‘lmagan ma’lumotlar tuzilishi deb hisoblanadi. Daraxt ma’lumotlar tuzilishiga extiyojlar: kompyuterdagi ma’lumotlar tuzilmasi(fayllar tizimi)ni qurilishida ma’lumotlar joylashuvi daraxtlar asosida 2
quriladi; kompilyator dizaynida dastur tuzilishini ifodalash uchun sintaksis daraxti ishlatiladi; B daraxtlari va boshqa daraxt tuzilmalari ma’lumotlar bazasini indekslashda ma’lumotlarni samarali qidirish va olish uchun ishlatiladi. Daraxt ma’lumotlar tuzilishining afvzalliklari: daraxtlar daraxt turiga qarab samarali qidirishni taklif qiladi, o‘rtacha qidirish vaqtlari O(log n) bo‘lib, ushbu usul AVL kabi muvozanatli daraxtlar uchundir; daraxtlar ma’lumotlarning ierarxik ko‘rinishini ta’minlaydi, bu esa katta hajmdagi ma’lumotlarni tartibga solish va boshqarishni osonlashtiradi; daraxtlarning rekursiv tabiati ularni rekursiv algoritmlar yordamida o‘tish va boshqarishni osonlashtiradi. Daraxt ma’lumotlar tuzilishining kamchiliklari: muvozanatsiz daraxtlar, ya’ni daraxtning balandligi bir tomonga qiyshaygan, bu esa qidiruv vaqtlarining samarasizligiga olib kelishi mumkin; daraxtlar massivlar va bog‘langan ro‘yxatlar kabi ba’zi boshqa ma’lumotlar tuzilmalariga qaraganda ko‘proq xotira maydonini talab qiladi, ayniqsa daraxt juda katta bo‘lsa; daraxtlarni amalga oshirish va manipulyatsiya qilish murakkab bo‘lishi mumkin va algoritmlarni yaxshi tushunishni talab qiladi. Fenvik daraxti daraxtlarning indekslangan turi bo‘lib, dasturlashda dasturchilarga kodni tuzishda yordam beradi va kodni tuzish va bajarishda xatoliklar kamayadi. Fenvik daraxti dasturchilarga kodni yozishda kerakli sintaksis va qoidalarni tushuntiradi va kodni to‘g‘ri yozishni osonlashtiradi. Bu qoidalarga amal qilish orqali, dasturchilar kodni to‘g‘ri yozishni osonlashtiradi va kodni tuzish va boshqa dasturlash vazifalarini bajarishda xatoliklar kamayadi. Fenvik daraxti Python dasturlash tilida ham qo‘llaniladi. Bu daraxt Python dasturlash tilida o‘zining sintaksisiga ega bo‘lib, dasturchilarga o‘zgaruvchan ma’lumotlar saqlash va ularga murojaat qilish imkoniyatini beradi. Fenvik daraxtining asosiy afvzalliklari quyidagilardan iborat: 3
o‘zgaruvchan va o‘zgarmas ma’lumotlar uchun xususiyatlarda; sintaksisda; yorqinligida; keng qo‘llanilishida; xavfsizligida; o‘ziga xos funksiyalarida; keng tarqalganligida; yangilanishlarni kuzatib borish juda ham qulay. Fenvik daraxtining asosiy kamchiliklari quyidagilardan iborat: tezlik; xotira sarflanishi; qiyinchilik; resurslar miqdorining cheklanganligi; o‘zgaruvchilardan foydalanishning noqulayligi. Dasturlashda Fenvik daraxtini o‘rganish juda ham zarur. Fenvik daraxti dasturlashda matematik masalalarni yechish, algoritmlar yaratish va ma’lumotlarni tahlil qilish uchun ishlatiladi. Shu tarzda, ishlab chiquvchilar muhim muammolarni hal qilishlari va dasturlarning yaxshiroq va samarali ishlashiga yordam berishlari mumkin. Fenvik daraxtida qo‘llaniluvchi o‘zgaruvchilar Fenvik o‘zgaruvchilar deb ataladi va Fenvik o‘zgaruvchilari dasturchilarga funksiya ichida aniqlanmagan va funksiyadan tashqarida aniqlangan o‘zgaruvchilarga kirishga imkon beradi. Bu dasturchilarga funksiyalar o‘rtasida ma’lumotlarni almashish va dasturning turli qismlari o‘rtasida ma’lumotlarni uzatish imkonini beradi. 4
FENVIK DARAXTI VA ALGORITMI 2.1 Fenvik daraxti haqida umumiy tushuncha Fenvik daraxti dasturlashda o‘zining o‘ziga xos xususiyatlari bilan ajratilgan. Bu xususiyatlar esa o‘zgaruvchan va o‘zgarmas bo‘lishi mumkin. Fenvik daraxti (ingliz tilidan olingan bo‘lib, “ikkilik indeksli daraxt” degan ma’noni anglatadi) – prefiks yig‘indisini samarali hisoblashi va elementlarni yangilashi mumkin bo‘lgan ma’lumotlar tuzilishi, saqlashni talab qiladigan ma’lumotlar tuzilishi O(n) o‘lchovli xotira va samarali hisoblangan quyidagi operatsiyalarni bajarish kabi bir qancha vazifalarni bajaradi: qatordagi istalgan elementning qiymatini osongina o‘zgartirish; [i, j] segmentdagi assotsiativ, komutativ, qiymat qaytaradigan operatsiyani bajarish(odatda bu yig‘indini hisoblovchi yig‘indi funksiyasi); Ikkilik daraxtning barglarida asl massivning qiymatlari, qolgan tugunlarida esa avlodlarning qiymatlari yig‘indisi saqlanadi. Fenvik daraxti yordamida har bir butun sonni ikki daraja yig‘indisi sifatida ifodalash mumkin. Xuddi shu tarzda, jami yig‘indini ushbu o‘zgaruvchan chastota to‘plamlari yig‘indisi sifatida hisoblash mumkin. Fenvik daraxtining strukturasi hamda unda yig‘indi funksiyasining qo‘llanilishi quyidagicha: vector<int> daraxt; int size; void increase(int index, int value) { for(int i=index; i<size; i = (i | (i+1))) daraxt[i] += value; } int sum(int right) 5