Algoritmlar va berilganlar strukturasi

Diapazon so'rovi
Har qanday berilgan indeksga ( "diapazon so'rovi" operatsiyasi) prefiks yig'indisini topish uchun joriy indeksdan daraxt ildizigacha bo'lgan yo'l bo'ylab tugunlar qiymatlarini qo'shing (bu arzimas bo'sh yig'indi, 0). Qo'shiladigan qiymatlar soni (yashirin ildizdan tashqari) indeksdagi 1 bitlar soniga teng va ko'pi bilan⌈jurnal2⁡n⌉  , vaqt murakkabligini berishO(jurnal⁡n)  .
Masalan, birinchi o'n bitta qiymatning yig'indisini topmoqchi bo'lsangiz, ayting. Eleven ikkilik tizimda 1011 _{2 ga teng. Bu uchta 1-bitni o'z ichiga oladi, shuning uchun uchta tugun qiymati qo'shilishi kerak: 11=1011 2} , 10=1010 ₂ va 8=1000 ₂ tugunlaridagilar (0000 ₂ ning yashirin ildiz tuguniga e'tibor bermaslik mumkin). Bular mos ravishda A[11], A[9,10] va A[1,8] summalarini o'z ichiga oladi (bu erda A[i,j] = {A[i], A[i+1], .. ., A[j]}).
Nuqtalarni yangilash
Indeksdagi Fenwick daraxtidagi qiymatni yangilash uchuni i (topshirishga mos keladiA[i] A[i] yangi qiymat) ( "nuqtani yangilash" operatsiyasi):

• 
  Deltani hisoblangd=A[i]new−A[i]old  .
  
• 
  Keyin, while indeksii≤n  :
  
  • 
    LSB qo'shish orqali indeksni yangilang:i←i+(i & (−i)) 
    
  • 
    Qo'shishd  tugundagi qiymatgai i.
    

Intuitiv ravishda, buni har bir tugunni yangilash deb hisoblash mumkin (i i va ortib borayotgan tartibda takrorlash) mas'uliyat doirasiga kiradiA[i] A[i].
Masalan, 16 elementli massivdagi 11=1011 _{2 qiymatini yangilash 1011 2} , (1011 ₂ + 1 ₂ = 1100 ₂ ) va (1100 ₂ + 100 ₂ = 10000 ₂ ) ni yangilashni talab qiladi. Bular mos ravishda A[11], A[9,12] va A[1,16] summalarini o'z ichiga oladi. Shunga qaramay, yangilanishi kerak bo'lgan tugunlarning maksimal soni massiv o'lchamidagi bitlar soni bilan cheklangan,⌈jurnal2⁡n⌉  , va vaqt murakkabligi shundayO(jurnal⁡n) O(log n)