logo

Fenvik daraxti va algoritmi

Загружено в:

12.08.2023

Скачано:

0

Размер:

98.0458984375 KB
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 {
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 Ushbu   daraxt   ma’lumot   tuzilmasi   birinchi   marta   Piter   Fenvik   tomonidan   1994-
yilda tasvirlangan.   Fenvik daraxti  o‘zining o‘ziga xos sintaksisiga  ega bo‘lib, bu
sintaksis   dasturchilarga   o‘zgaruvchan   ma’lumotlar   saqlash   va   ularga   murojaat
qilish   imkoniyatini   beradi.   Fenvik   daraxti   yordamida   dasturchilar   o‘zgaruvchan
ma’lumotlar   ustida   turli   amallar   bajarishlari   mumkin,   masalan,   ularga   yangi
qiymatlar   tayinlash,   ulardan   ma’lumot   o‘qish,   ulardan   ma’lumot   o‘chirish   va
hokazo.   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 dasturlashda quyidagi afvzalliklari mavjud:
 O‘zgaruvchan   va   o‘zgarmas   ma’lumotlar   uchun   xususiyatlar:   Fenvik
daraxti   o‘zgaruvchan   va   o‘zgarmas   ma’lumotlar   uchun   xususiyatlar   bilan
ajratilgan. 
 Sintaksis:   Fenvik   daraxti   o‘ziga   xos   sintaksisga   ega   bo‘lib,   bu   sintaksis
dasturchilarga o‘zgaruvchan ma’lumotlar saqlash va ularga murojaat qilish
imkoniyatini beradi.
 Yorqinlik:   Fenvik   daraxti   yorqin   va   sodda   sintaksisga   ega   bo‘lib,   bu
dasturchilar uchun o‘rganishni oson qiladi.
 Keng   qo‘llanilishi:   Fenvik   daraxti   Python,   C++,   Java   va   boshqa   ko‘plab
dasturlash tillarida qo‘llaniladi. 
 Xavfsizlik:   Fenvik   daraxti   xavfsizlikni   oshirish   uchun   yordam   beradi.
Misol   uchun,   o‘zgaruvchan   ma’lumotlar   ustida   amallar   bajarishda
xatoliklar   sodir   bo‘lishi   mumkin,   ammo   Fenvik   daraxti   xatoliklarni   oldini
olish uchun xavfsizlikni oshirish imkoniyatini beradi. 
 O‘ziga xos funksiyalari: Fenvik daraxtli  o‘zining o‘ziga xos funksiyalarga
ega bo‘lib, bu funksiyalar  dasturchilarga o‘zgaruvchan ma’lumotlar  ustida
turli amallar bajarish imkoniyatini beradi.
 Yorliq:   Fenvik   daraxti   yorliq   yordamida   dasturchilarga   dastur   yozishda
yordam beradi.
7  Keng tarqalgan:  Fenvik daraxti  ko‘plab dasturlash  tillarida keng  tarqalgan
bo‘lib, bu dasturchilarga o‘rganish va ishlatishda yordam beradi.
Fenvik   o‘zgaruvchilar   -   bu   funksiya   ichida   aniqlanmagan   va   funksiyadan
tashqarida   aniqlangan   o‘zgaruvchilar.   Ushbu   o‘zgaruvchilar   dasturchilarga
funksiyalar   o‘rtasida   ma’lumotlarni   almashish   va   dasturning   turli   qismlari
o‘rtasida ma’lumotlarni uzatish imkonini beradi.
Fenvik o‘zgaruvchilardan foydalanishning afzalliklari: 
 bu   dasturchilarga   funksiyalar   o‘rtasida   ma’lumotlarni   almashish   imkonini
beradi; 
 bu   dasturning   turli   qismlari   o‘rtasida   ma’lumotlarni   to‘g‘ri   uzatishni
osonlashtiradi; 
 bu dasturchilarga kamroq kod yozish imkonini beradi.
Fenvik   o‘zgaruvchilari   dasturlashda   juda   muhimdir   va   chastota
o‘zgaruvchilari   ushbu   funksiyalarning   ishlashiga   ta’sir   qilishi   mumkin.   Fenvik
o‘zgaruvchilar   -   bu   funksiya   ichida   aniqlanmagan   va   funksiyadan   tashqarida
aniqlangan   o‘zgaruvchilar.   Fenvik   o‘zgaruvchilarining   asosiy   kamchiligi
shundaki,   ular   dasturning   o‘qilishini   sekinlashtiradi.   Funksiya   ichida
ishlatiladigan   o‘zgaruvchining   qayerdan   kelib   chiqqanligini   tushunish   qiyin
bo‘lishi   mumkin,   bu   esa   dasturni   saqlashni   qiyinlashtirishi   mumkin.   Bundan
tashqari, fenvik o‘zgaruvchilari dasturning aniqligiga ham  ta’sir qilishi  mumkin.
Masalan,   agar   funksiya   ichida   ishlatiladigan   Fenvik   o‘zgaruvchisi   tasodifan
boshqa joyga o‘zgartirilsa, funksiya natijasi noto‘g‘ri bo‘lishi mumkin. Natijada,
dasturlash tilida fenvik o‘zgaruvchilaridan foydalanishni iloji boricha kamaytirish
kerak.   Funksiyalarda   ishlatiladigan   o‘zgaruvchilar,   iloji   bo‘lsa,   funksiya
parametrlari sifatida aniqlanishi kerak.
Fenvik   daraxti   yoki   ikkilik   indekslangan   daraxt   -   ko‘p   vazifalarda
segmentlar   daraxtini   almashtiradigan,   lekin   ayni   paytda   3-4   baravar   tezroq
8 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 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 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 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 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 Fenvik   daraxtini   segment   daraxt   ma’lumot   tuzilmalari   bilan   taqqoslashda
uning afvzalliklari va kamchiliklari quyidagicha:
Afvzalliklari:
• yuqorida aytib o‘tilgan soddalik va tezlik;
• xotira O(n)ni oladi;
• Fenvik   daraxti   segmentlar   daraxtiga   qaraganda   bir   marta   kamroq   xotirani
doimiy   ravishda   egallaydi.   Buning   sababi   shundaki,   Fenvik   daraxti   faqat
ba’zi elementlar  uchun operatsiya qiymatini saqlaydi  va segmentlar  daraxti
elementlarning   o‘zini   va   operatsiyaning   qisman   natijalarini   pastki
kesmalarda   saqlaydi,   shuning   uchun   u   kamida   ikki   baravar   ko‘p   xotirani
oladi;
• Fenvik daraxtini amalga oshirish osonroq;
• Fenvik daraxti qurilayotgan segmentdagi operatsiya qaytarilishi kerak, ya’ni
segmentdagi minimal (maksimal kabi) bu daraxtni segment daraxtidan farqli
o‘laroq   hisoblash   mumkin   emas.   Ammo   agar   biz   prefiksda   minimal
miqdorni topishimiz kerak bo‘lsa, unda Fenvik daraxti bu vazifani bajaradi.
Bunday   Fenvik   daraxti   massiv   elementlarini   kamaytirish   operatsiyasini
qo‘llab-quvvatlaydi.   Daraxtdagi   minimalni   qayta   hisoblash   prefiksdagi
minimum massivini yangilashdan ko‘ra tezroq
Kamchiliklari:
•   funksiya   ma’lumot   qaytarishi   kerak   bo‘lgan   ayrim   holatlarda   ma’lumotlar
topilmay   qolishi   mumkin,   ya’ni   bu   daraxt   minimal   va   maksimal   darajada
hisoblay   olmaydi   (ba’zi   ma’lumotlarni   yo‘qotishimiz   bo‘lgan   holatlar
bundan mustasno).
14 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 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 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 raqamlar qatori bo‘yicha samarali so‘rovlar va yangilanishlarni amalga oshirishga
imkon beradigan ma’lumotlar tuzilishi.
Dastur   kerakli   sarlavha   fayllarini   qo‘shish   va   ba’zi   o‘zgaruvchilarni   e’lon
qilish bilan boshlanadi. ’N’ o‘zgaruvchi massiv hajmini, `a` massivning o‘zi va `f``
esa Fenvik daraxtidir.
’Get_min’   funksiyasi   massiv   oralig‘idagi   minimal   qiymatni   topish   uchun
ishlatiladi.   U   oraliqdagi   oxirgi   element   indeksini   ifodalovchi   kirish   sifatida   `x   ’
butun sonni oladi. Keyin funktsiya `x` dan boshlab va orqaga qarab ildizga qarab
daraxt ustida takrorlanadi va duch kelgan minimal qiymatni qaytaradi.
’Assign’   funksiyasi   massivdagi   element   qiymatini   yangilash   uchun
ishlatiladi. Kirish sifatida ikkita butun son olinadi, ’idx’ va ’val’, ular mos ravishda
yangilanadigan   element   indeksini   va   tayinlanadigan   yangi   qiymatni   ifodalaydi.
Funksiya   massivdagi   elementning   qiymatini   yangilaydi   va   keyin   Fenvik
daraxtidagi tegishli tugunlarni yangilaydi.
’Main’ funktsiyasi massiv hajmida o‘qiydi va Fenvik daraxtini `INT_MAX`
qiymatlari   bilan   boshlaydi.   Keyin   u   massiv   elementlarida   o‘qiydi   va   ` assign `
funksiyasi yordamida Fenvik daraxtini mos ravishda yangilaydi.
18 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 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 Bu C++ dasturi, bir nechta sonlardan iborat bo‘lgan ketma-ketlikda eng uzun
o‘sishni topish uchun yozilgan. Dasturda,   a   va   f   nomli ikkita massiv ishlatiladi.   a
massivi,   ketma-ketlikdagi   har   bir   sonni   saqlaydi,   f   massivi   esa,   a   massivida
berilgan indeksdagi sonni o‘z ichiga olgan eng katta sonni saqlaydi.
Dasturda,  get_max  funksiyasi, berilgan indeksdan boshlab orqaga qaytib,
f   massivida   eng   katta   sonni   topadi.   assign   funksiyasi   esa   berilgan   indeksdagi
qiymatni   a   massiviga   yozadi   va   f   massivida   mos  keladigan  indekslarga  eng katta
qiymatlarni yozadi.
Dasturda   seq   nomli   massivga   foydalanuvchi   tomonidan   sonlar   kiritiladi.
Keyin   har   bir   son   uchun   eng   uzun   o‘sishni   topish   uchun,   get_max   funksiyasi
yordamida   avvalgi   sonlardan   eng   katta   sonni   topib,   keyin   assign   funksiyasi
yordamida   eng   uzun   o‘sishni   hisoblash   uchun   mos   keladigan   qiymatlarni   a   va   f
massivlariga   yozadi.   Natijada,   get_max   funksiyasi   yordamida   eng   katta   sonni
topib, konsolga chiqaradi.
21 2.3   Fenvik daraxt strukturasini yaratish bo‘yicha umumiy
ko‘rsatmalar
Fenvik daraxt   strukturasi quyidagi bosqichlarda yaratiladi:
1. Massivdagi   elementlar   uchun   Fenvik   daraxt   massivi   yaratiladi.   Fenvik
daraxt   massivi,   massivdagi   elementlar   sonidan   bir   necha   bit   ko‘p   bo‘lgan
massivdir.
2. Fenvik   daraxt   massivining   har   bir   elementi,   massivdagi   bir   necha
elementning kumulyativ yig‘indisini saqlaydi.
3. Kumulyativ   yig‘indini   hisoblash   uchun,   Fenvik   daraxt   massivida   bir   necha
elementni   qo‘shish   kerak   bo‘ladi.   Bu   elementlar,   massivdagi   elementlar
sonidan bir necha bit ko‘p bo‘lgan elementlar hisoblanadi
4. Kumulyativ   yig‘indini   hisoblash   uchun,   Fenvik   daraxt   massivida   bir   necha
elementni   qo‘shish   kerak   bo‘ladi.   Bu   elementlar,   massivdagi   elementlar
sonidan bir necha bit ko‘p bo‘lgan elementlar hisoblanadi.
5. Kumulyativ   yig‘indini   hisoblash   uchun,   Fenvik   daraxt   massivida   bir   necha
elementni   qo‘shish   kerak   bo‘ladi.   Bu   elementlar,   massivdagi   elementlar
sonidan bir necha bit ko‘p bo‘lgan elementlar hisoblanadi.
6. Fenvik   daraxt   massivida   kumulyativ   yig‘indini   hisoblash   uchun   kerak
bo‘lgan barcha elementlar hisoblanadi.
Fenvik  daraxt   strukturasi   massivdagi   elementlar   sonidan  bir   necha  bit  ko‘p
bo‘lgan   holatlarda   kumulyativ   yig‘indinini   tez   hisoblash   uchun   juda   samarali
hisoblanadi.
22 XULOSA
Xulosa   o‘rnida   aytilsa,   biz   elementlarning   yig‘indisi   bo‘yicha   so‘rovlarga
javob   berishni   va   har   qanday   elementni   logarifmik   vaqt   ichida   o‘zgartirishni
o‘rgandik. Ushbu algoritmlar juda ko‘p foydalanishga ega va operatsiya natijasini
tezda   o‘zgartirish   va   aniqlash   kerak   bo‘lgan   barcha   vazifalarda   yordam   berishi
mumkin.   Ehtimol,   ushbu   tuzilmani   qanday   yozishni   biladiganlarning   to‘rtdan
biridan kamrog‘i uning qanday ishlashini to‘liq tushunishadi. Tahlil haqiqatan ham
juda   murakkab   bo‘lgani   uchun   mavhumlashtirish   degan   ishonchni   qabul   qilish
tavsiya   etiladi.   Fenvik   daraxti   bizning   operatsiyamiz   qaytarilganda,   shuningdek
prefiks yig‘indisi hiylasi ishlaganda ishlatilishi mumkin.   Fenvik daraxtini ishlatish
orqali   massivdagi   elementlarning   yig‘indisini   hisoblash   va   o‘zgartirish   uchun
kerak bo‘lgan ma’lumotlarning xotiradan egallagan hajmini tejab qolish mumkin.
Shuningdek,   Fenvik   daraxtini   ishlatish   orqali   massivdagi   elementlarning
yig‘indisini hisoblash va o‘zgartirish uchun kerak bo‘lgan vaqtni ham kamaytirish
mumkin.   Bu   odatda   xor   moduli(   |   )   bo‘yicha   yig‘indi,   ko‘paytirish   kabi   oddiy
operatsiyalar (agar  ushbu modulga hech narsa bo‘linmasligi  kafolatlangan bo‘lsa)
bo‘lganda qo‘llaniladi. Fenvik daraxti(yoki binary indexed tree) nomli ma’lumotlar
strukturasini   ishlatish   orqali   massivdagi   elementlarning   qiymatlarini   saqlash,
o‘zgartirish   va   ularning   yig‘indisini   hisoblash   mumkin.   Bu   struktura   massivdagi
elementlarning qiymatlarini saqlash uchun juda kam xotira kerakligini ta’minlaydi
va   shuningdek,   massivdagi   elementlarning   yig‘indisini   hisoblash   uchun   ham
yaxshi natijalar beradi.   Fenvik daraxti massivdagi har bir elementni bir necha bitta
daraxtga bog‘lash orqali yaratiladi. Daraxtning har bir tugunida, tugunni o‘z ichiga
olgan elementlar yig‘indisi saqlanadi. Bu yig‘indilar daraxtning ajdod tugunlariga
qo‘shilgan   holda     massivdagi   bir   necha   elementning   yig‘indisini   ifodalaydi.
Element   qiymati   o‘zgartirilganda,   uni   o‘z   ichiga   olgan   daraxtdagi   tugunlar   ham
yangilangan   hisoblanadi.   Kumulativ   yig‘indi   –   yig‘indini   oshiruvchi   yig‘indi.
Fenvik   daraxti   massivdagi   qiymatlarning   kumulativ   yig‘indi   va   boshqa   statistik
ma’lumotlarni tez hisoblash uchun ishlatiladi. 
23 Ushbu   ma’lumotlar   strukturasining   amaliyotda   bir   nechta   sohalari   mavjud:
kumulativ yig‘indini hisoblash: 
 Fenvik   daraxti   massivdagi   har   bir   elementning   qiymatini   o‘z   ichiga   olgan
daraxtdagi tugunlar yig‘indisi orqali hisoblaydi. Bu, massivdagi  har qanday
elementning kumulativ yig‘indini tez hisoblash uchun yaxshi usuldir.
 Massivdagi   har   qanday   elementni   o‘zgartirish:   Fenvik   daraxti   massivdagi
har   qanday   elementni   o‘zgartirish   uchun   ham   ishlatiladi.   Element   qiymati
o‘zgartirilganda, uni  o‘z  ichiga olgan daraxtdagi  tugunlar  ham  yangilangan
holda yana hisoblanadi.
 Massivdagi   har   qanday   elementni   o‘qish:   Fenvik   daraxti   massivdagi   har
qanday   elementning   qiymatini   o‘qish   uchun   ham   ishlatiladi.   Elementning
qiymati,   uni   o‘z   ichiga   olgan   daraxtdagi   tugunlar   yig‘indisi   orqali
hisoblanadi.
 Bir necha elementning yig‘indisini hisoblash: Fenvik daraxti massivdagi bir
necha   elementning   yig‘indisini   hisoblash   uchun   ham   ishlatiladi.   Bir   necha
elementning   yig‘indisi,   ularning   daraxtdagi   tugunlar   yig‘indisi   orqali
hisoblanadi.
Fenvik   daraxti   amaliyotda   katta   ma’lumotlar   to‘plamlarini   ishlab   chiqish,
statistik   analizlar,   matematik   hisob-kitob   va   boshqa   sohalarda   ham   ishlatiladi.
Masalan, Fenvik daraxti matritsa elementlarining yig‘indisini hisoblash uchun ham
ishlatiladi.
Fenvik daraxti amaliyotda tez va samarali hisob-kitob uchun juda muhimdir.
Ushbu   ma’lumotlar   strukturasining   yordamida   massivdagi   har   qanday   elementni
o‘zgartirish, o‘qish va bir necha elementning yig‘indisini hisoblash uchun O(logn)
vaqt talab qilinadi.
Fenvik   daraxt(yoki   Binary   Indexed   Tree)   ma’lumotlar   strukturasini
ishlatmasangiz, siz ma’lumotlar yig‘indisini hisoblash uchun boshqa algoritmlar va
strukturalardan   foydalanishingiz   mumkin.   Siz   ma’lumotlar   yig‘indisini   hisoblash
uchun odatda "prefix sum" algoritmini ishlatasiz. Bu algoritm, bir massivning har
24 bir   elementining   qiymatini   o‘zidan   oldingi   elementning   qiymati   bilan   qo‘shib
boradi.   Bunday   qilib,   siz   massivning   har   bir   elementining   kumulativ   yig‘indisini
hisoblash uchun o‘zgaruvchilarni qo‘shib borishingiz mumkin. 
Fenvik   daraxtidan   foydalanish   o‘rnida   Segment   daraxt(yoki   Interval   Tree)
ma’lumotlar   strukturasini   ishlatish   ham   mumkin.   Segment   daraxti   ma’lumotlar
yig‘indisini   hisoblash   uchun   ham   yaxshi   ishlaydi   va   Fenvik   daraxtidan
foydalanishdan   boshqa   variantlardan   biridir.   Boshqa   algoritmlar   va   strukturalar
ham   mavjud,   shuningdek,   siz   ma’lumotlar   yig‘indisini   hisoblash   uchun
o‘zgaruvchilarni   qo‘shib   borish   yoki   boshqa   yordamchi   strukturalardan
foydalanishingiz mumkin.
Fenvik daraxtini qo‘llashda uning muhimligi qay darajada ekanligini anglab
yetish   zarur,   chunki   ushbu   ma’lumot   tuzilmasi   ham   boshqa   ma’lumot   tuzilmalari
kabi murakkab tuzilmagan bo‘lib, Fenvik daraxtini qo‘llash xatolardan holi emas.
Aslini   olganda   hech   bir   ma’lumot   tuzilmasi   murakkab   tuzilmagan   bo‘lib,
ma’lumotlar   tuzilmalarining   dasturda   qo‘llanilishida   yagona   tuzilmadan
foydalanilmaydi. Bundan kelib chiqadiki, Fenvik daraxtini qo‘llashda ham, Fenvik
daraxti ma’lumotlar tuzilmasiga mos, hamda uning kamchiliklarini bartaraf etuvchi
ma’lumot   tuzilmalari   bilan   mutanosib   holatda   qo‘llash   tavsiya   etiladi.   Fenvik
daraxtining   eng   asosiy   afvzalligi   uning   ma’lumotlarni   saqlash   tuzilmasini   tashkil
qilishning nihoyatda sodda, ma’lumotlarga o‘zgartirish kiritish oson hamda qulay
hisoblanar   ekan,   uni   qo‘shimcha   tuzilmalar   bilan   birgalikda   qo‘llay   olish   orqali
katta yutuqlarga erishish mumkin.
25 FOYDALANILGAN ADABIYOTLAR:
4.1   Ijtimoiy sahifalar va saytlarda mavjud adabiyotlar:
-   https://algorithmica.org/ru/fenwick    ;
- https://habr.com/ru/articles/112828/    ;
- https://uz.zahn-info-portal.de/wiki/Fenwick_tree    ;
- https://brestprog.by/topics/fenwicktree/    ;
- https://neerc.ifmo.ru/wiki/index.php?   
title=Многомерное_дерево_Фенвика ;
- https://digitrain.ru/articles/244795/    ;
- https://ppt-online.org/949421    ;
- https://algoprog.ru/material/fenwick    ;
- https://ru.algorithmica.org/cs/range-queries/fenwick/    ;
- https://neerc.ifmo.ru/wiki/index.php?title=Дерево_Фенвика    ;
26

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