Segment tree va Fenwick tree: o'zgaruvchan massivda oraliq so'rovlari O(log n) da

Qisqacha: Massiv o'zgarib tursa va "l dan r gacha yig'indi" kabi so'rovlar ko'p bo'lsa, oddiy massiv (so'rov O(n)) ham, prefix sum (yangilash O(n)) ham sekin. Segment tree har tugunda bir oraliqning tayyor yig'indisini saqlaydi: so'rov ham, yangilash ham O(log n). U yig'indi, minimum, maksimum — istalgan "birlashtiriladigan" amal uchun ishlaydi. Fenwick tree (BIT) — faqat yig'indi kabi amallar uchun, lekin juda qisqa: n + 1 katakli massiv va i & -i hiylasi.

Bu darsda

• Nega prefix sum o'zgaruvchan ma'lumotda yaramasligini va qanday so'rovlar aralashmasida qaysi tuzilma kerakligini tushuntira olasiz.
• Segment tree qurish, oraliq yig'indisi va nuqtaviy yangilashni yozasiz va qadamma-qadam kuzatasiz.
• Yig'indini minimumga almashtirib, oraliq minimumi daraxtini yasay olasiz.
• Fenwick tree'ni i & -i bilan yozasiz va to'rt yechimni o'lchab solishtirasiz.

Oldin bilishingiz kerak: Prefix sum va difference array, Priority queue va heap naqshlari, Bitwise operatorlar, Daraxt masalalari.

1. Nega bu kerak?

«Bahor» buxgalteri har kungi tushumni massivda saqlaydi: days[i] — i-kunning tushumi. Jasur aka tez-tez so'raydi: "3-kundan 10-kungacha qancha ishladik?" Bu — oraliq so'rovi (range query).

Prefix sum darsida bu savolga O(1) da javob berishni o'rgandik. prefix[i] — 0-kundan i − 1-kungacha jami. Oraliq yig'indisi — ikki prefiksning ayirmasi. Lekin bitta shart bor edi: massiv o'zgarmaydi.

Hayotda esa o'zgaradi. Mehmon pulini qaytarib oldi — 5-kun tushumi kamaydi. Kassir xato kiritgan edi — 3-kun tuzatildi. Har tuzatishdan keyin prefix massivini 5-kundan oxirigacha qayta hisoblash kerak — O(n). Kun bo'yi minglab so'rov va minglab tuzatish aralash kelsa:

Birinchi ikkitasida bitta amal tez, ikkinchisi sekin — xuddi heap darsi boshidagi kabi. Javob ham o'xshash: ikkala amalni O(log n) qiladigan daraxt.

2. Segment tree g'oyasi

2.1 Tayyor bo'laklar

«Bahor» buxgalterining kassa daftarini tasavvur qiling. Har kunlik tushumdan tashqari, haftalik, oylik va choraklik jami ham oldindan yozilgan. Jasur aka "Martdan maygacha qancha?" deb so'rasa, buxgalter 92 ta kunni qo'shmaydi — uchta oylik jamini qo'shadi. Bir kun tuzatilsa — faqat o'sha kunning haftasi, oyi, choragi va yili qayta yoziladi. Qolgan oylarning jami o'zgarmaydi.

Segment tree (segmentlar daraxti) — shu g'oyaning daraxt ko'rinishi:

• ildiz — butun massiv (0-kundan n − 1-kungacha) yig'indisi;
• har tugun o'z oralig'ini ikkiga bo'ladi: chap bola — chap yarmi, o'ng bola — o'ng yarmi;
• barglar — bitta kun.

8 kunlik daraxtda 15 ta tugun bo'ladi: 8 ta barg, 4 ta "ikki kunlik", 2 ta "to'rt kunlik" va ildiz. Umuman olganda, tugunlar 2n − 1 ta, balandlik — log₂ n atrofida.

2.2 Massivda saqlash

Tugunlarni binar daraxt darsidagi kabi { value, left, right } obyektlari bilan ham yasash mumkin edi. Lekin Heap dagidek massiv qulayroq: havolalar yo'q, bolani formula topadi. Bu yerda indekslar 1 dan: ildiz — tree[1], k-tugunning bolalari — tree[2k] va tree[2k + 1]. 0-katak ishlatilmaydi. 1 dan boshlasak, formulalar heap'dagidan ham soddaroq bo'ladi.

Massiv uzunligi — 4n. Nega 2n emas? Kunlar soni ikkining darajasi bo'lmasa, daraxt "teshikli" bo'ladi. Oxirgi qavatdagi ba'zi tugunlar katta raqamli kataklarga tushadi. Masalan, 6 kunda oxirgi barg 13-katakka tushadi, 2n esa atigi 12. 4n esa har qanday n uchun yetishi isbotlangan — xavfsiz zaxira. Xotira baribir O(n).

3. Kod: qurish, so'rov, yangilash

3.1 Qurish

#build rekursiv: oraliqni ikkiga bo'ladi, ikkala yarmini quradi, keyin o'z yig'indisini bolalaridan hisoblaydi. Bu Daraxt masalalari darsidagi "pastdan tepaga" naqsh. Har tugun bir marta hisoblanadi — O(n).

3.2 So'rov

sum(l, r) ildizdan boshlaydi. Har tugunda uch holatdan biri:

1. Tugun oralig'i so'rov bilan kesishmaydi — 0 qaytaradi, pastga tushmaydi.
2. Tugun oralig'i so'rov ichida to'liq — tayyor yig'indisini qaytaradi, pastga tushmaydi.
3. Qisman kesishadi — ikki bolasiga bo'linadi va javoblarni qo'shadi.

Kuzating: 8 kunlik tushum (mln so'm), so'rov — 2-kundan 6-kungacha. Tugun ostidagi yozuv — uning kunlar oralig'i; yashil — olingan tayyor bo'laklar:

5 kunlik yig'indi uchta tayyor bo'lakdan yig'ildi. Nega har doim O(log n)? Isbotlash mumkinki, har qavatda "qisman" holatdagi tugunlar ko'pi bilan ikkita bo'ladi — so'rov oralig'ining chap va o'ng chetlari. Shuning uchun har qavatda ko'pi bilan 4 ta tugunga tegiladi, qavatlar esa log₂ n ta.

3.3 Yangilash

set(i, value) i-bargga qadar tushadi (qidiruv kabi: i <= mid — chapga, aks holda o'ngga), uni yozadi va qaytishda yo'ldagi har otaning yig'indisini qayta hisoblaydi. Boshqa tugunlarga i-kun kirmaydi — ular o'zgarmaydi:

Yo'l uzunligi — balandlik + 1, ya'ni O(log n). Million kunlik massivda — 21 ta tugun.

Tekshirib ko'ring: 8 kunlik daraxtda sum(0, 7) so'roviga nechta tugunga qaraladi? sum(3, 3) ga-chi?

3.4 Butun klass va ishlatish

class SegmentTree {
  constructor(values) {
    this.n = values.length;
    this.tree = new Array(4 * this.n).fill(0); // 1 — ildiz
    if (this.n > 0) this.#build(values, 1, 0, this.n - 1);
  }
  #build(values, node, lo, hi) {
    if (lo === hi) {
      this.tree[node] = values[lo]; // barg — bitta kun
      return;
    }
    const mid = Math.floor((lo + hi) / 2);
    this.#build(values, 2 * node, lo, mid);
    this.#build(values, 2 * node + 1, mid + 1, hi);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
  sum(l, r, node = 1, lo = 0, hi = this.n - 1) {
    if (r < lo || hi < l) return 0; // kesishmaydi
    if (l <= lo && hi <= r) return this.tree[node]; // to'liq ichida
    const mid = Math.floor((lo + hi) / 2);
    return (
      this.sum(l, r, 2 * node, lo, mid) +
      this.sum(l, r, 2 * node + 1, mid + 1, hi)
    );
  }
  set(i, value, node = 1, lo = 0, hi = this.n - 1) {
    if (lo === hi) {
      this.tree[node] = value;
      return;
    }
    const mid = Math.floor((lo + hi) / 2);
    if (i <= mid) this.set(i, value, 2 * node, lo, mid);
    else this.set(i, value, 2 * node + 1, mid + 1, hi);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
}

// 8 kunlik tushum, mln so'm
const days = new SegmentTree([5, 3, 7, 2, 6, 4, 8, 1]);
console.log(days.sum(2, 6)); // 27
days.set(3, 9); // 3-kun tuzatildi
console.log(days.sum(2, 6)); // 34
console.log(days.sum(0, 7)); // 43

Rekursiv metodlar parametrlarining sukut qiymatlari bor: node = 1, lo = 0, hi = this.n - 1. Foydalanuvchi faqat sum(2, 6) yozadi, ichki chaqiruvlar esa qolganini o'zi beradi (Funksiya parametrlari). Rekursiya chuqurligi — log₂ n, million elementda 21: stek to'lishidan qo'rqmasa bo'ladi.

Endi o'zingiz hisoblang. 1 000 000 kunlik segment tree'da bitta set ko'pi bilan ta tugunni yangilaydi (balandlik + 1; 2²⁰ ≈ million).

4. Yig'indidan boshqa amallar

Segment tree faqat yig'indi uchun emas. Tugunda ikki bolaning natijasini birlashtirish mumkin bo'lgan har qanday amal ishlaydi: minimum, maksimum, EKUB, "nechta nol bor". Shart: amal assotsiativ bo'lsin — (a ∘ b) ∘ c = a ∘ (b ∘ c), ya'ni guruhlash tartibi natijani o'zgartirmasin. Bu yerda ∘ — istalgan amal o'rniga turgan belgi.

Misolda ko'ramiz. Minimum: min(min(5, 3), 7) = 3 va min(5, min(3, 7)) = 3 — bir xil. Segment tree oraliqni qanday bo'laklarga bo'lmasin, natija to'g'ri chiqadi. Ayirish esa assotsiativ emas: (10 − 4) − 3 = 3, lekin 10 − (4 − 3) = 9. Uni segment tree'ga solib bo'lmaydi. Yana kesishmaydigan tugun uchun betaraf qiymat kerak — natijaga ta'sir qilmaydigan son. Yig'indi uchun bu 0, minimum uchun — Infinity.

Kod uch joyda o'zgaradi: boshlang'ich qiymat Infinity, birlashtirish Math.min, kesishmaydigan tugun — Infinity. Mashqlarda o'zingiz yozasiz: "2-kundan 6-kungacha ko'k choyning eng arzon narxi".

Minimum uchun prefix sum hiylasi umuman ishlamaydi: ikki prefiks minimumidan oraliq minimumini chiqarib bo'lmaydi. Masalan, 0–6-kunlar minimumi 2, 0–1-kunlarniki 3. Bundan 2–6-kunlar minimumi haqida hech narsa bilib bo'lmaydi. Agar massiv o'zgarmasa, maxsus tuzilma (sparse table — kursda alohida o'rganmaymiz, hozir bilish shart emas) O(1) beradi. O'zgaradigan massivda esa segment tree — asosiy vosita.

Tekshirib ko'ring: Oraliq maksimumi uchun segment tree yasash mumkinmi? Kesishmaydigan tugun nima qaytarishi kerak?

5. Fenwick tree (BIT)

5.1 G'oya

Fenwick tree (yoki BIT — Binary Indexed Tree, "ikkilik indeksli daraxt") — 1994-yilda Piter Fenvik taklif qilgan tuzilma. U faqat prefiks yig'indisi savoliga javob beradi: "1-kundan i-kungacha jami". Oraliq yig'indisi esa prefix sum darsidagi kabi ikki prefiksning ayirmasi: prefix(r) - prefix(l - 1).

Hiyla — har katak turli uzunlikdagi bo'lak yig'indisini saqlaydi. tree[i] da — i-kun bilan tugaydigan, uzunligi i & -i bo'lgan bo'lak. i & -i — i ning ikkilik yozuvidagi eng o'ngdagi 1-bit qiymati (Bitwise operatorlar):

Bu hiylani Bit manipulyatsiya darsida bir marta ko'rgan edik: 6 & -6 = 2. Endi uni sekin, qadamma-qadam ochamiz — Fenwick butunlay shunga tayanadi.

JavaScript bitli amallarda sonni 32 bitli ikkiga to'ldirilgan (two's complement) shaklda ko'radi. Bu shaklda manfiy son shunday yasaladi: avval hamma bitlar teskarisiga aylantiriladi (~), keyin 1 qo'shiladi. 6 misolida (ko'rinish uchun faqat oxirgi 8 bit):

// sonning oxirgi 8 biti (255 = 11111111)
const bits = (x) => (x & 255).toString(2).padStart(8, "0");
console.log(bits(6)); // 00000110
console.log(bits(~6)); // 11111001
console.log(bits(-6)); // 11111010
console.log(bits(6 & -6)); // 00000010
console.log(6 & -6, 12 & -12, 7 & -7); // 2 4 1

Qatorma-qator kuzating:

1. 6 — 00000110. Eng o'ngdagi 1 — o'ngdan ikkinchi o'rinda.
2. ~6 — hamma bit teskari: 11111001. Endi o'sha o'rinda 0, undan o'ngdagilar esa 1.
3. -6 = ~6 + 1. Bir qo'shilganda o'ngdagi 1 lar "o'tkazish" bilan 0 ga aylanadi va o'sha o'rinda yana 1 paydo bo'ladi: 11111010.
4. 6 & -6 — ikkalasida ham 1 turgan joylar. Chap tomonda bitlar teskari, o'ng tomonda ikkalasida 0. Faqat bitta o'rinda ikkalasi ham 1: 00000010 = 2.

Xulosa: i & -i — i dagi eng o'ngdagi 1-bitning qiymati. 12 (1100) uchun 4, 7 (0111) uchun 1. Endi bu qiymatni "bo'lak uzunligi" deb o'qiymiz. 8 kunlik Fenwick'da har katak qaysi kunlarni qamraydi — kodning o'zi chiqarsin:

for (let i = 1; i <= 8; i++) {
  const len = i & -i; // bo'lak uzunligi
  console.log(`tree[${i}]: ${i - len + 1}–${i}-kunlar`);
}

Konsolda:

tree[1]: 1–1-kunlar
tree[2]: 1–2-kunlar
tree[3]: 3–3-kunlar
tree[4]: 1–4-kunlar
tree[5]: 5–5-kunlar
tree[6]: 5–6-kunlar
tree[7]: 7–7-kunlar
tree[8]: 1–8-kunlar

Toq kataklar — bitta kun. 2 va 6 — ikki kunlik bo'lak, 4 — to'rt kunlik, 8 — hammasi. Bu yana o'sha kassa daftari: kunlik, "ikki kunlik", haftalik jami — faqat segment tree'dagidan ikki baravar ixcham.

5.2 Kod

class Fenwick {
  constructor(n) {
    this.tree = new Array(n + 1).fill(0); // 1 dan boshlanadi
  }
  add(i, delta) {
    // i-kunga delta qo'shiladi (kunlar 1 dan)
    for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
  }
  prefix(i) {
    // 1-kundan i-kungacha yig'indi
    let total = 0;
    for (; i > 0; i -= i & -i) total += this.tree[i];
    return total;
  }
  rangeSum(l, r) {
    return this.prefix(r) - this.prefix(l - 1);
  }
}

const days = new Fenwick(8);
[5, 3, 7, 2, 6, 4, 8, 1].forEach((v, i) => days.add(i + 1, v));
console.log(days.prefix(7)); // 35
console.log(days.rangeSum(3, 7)); // 27
days.add(4, 7); // 4-kun: 2 → 9 (farq +7)
console.log(days.rangeSum(3, 7)); // 34

Ikkita sikl — butun daraxt shu:

• prefix(i): tree[i] ni qo'shamiz va i -= i & -i — shu bo'lakdan oldingi bo'lakka sakraymiz. Har sakrashda eng o'ngdagi 1-bit o'chadi — ko'pi bilan log₂ n qadam.
• add(i, delta): i-kunni o'z ichiga olgan hamma bo'laklarni yangilaymiz: i += i & -i. Bu ham ko'pi bilan log₂ n qadam.

add ni qo'lda yuramiz: 3-kunga 5 qo'shildi, n = 8.

• i = 3 (011): tree[3] (3-kun) yangilanadi, keyin 3 + 1 = 4.
• i = 4 (100): tree[4] (1–4-kunlar) yangilanadi, keyin 4 + 4 = 8.
• i = 8 (1000): tree[8] (1–8-kunlar) yangilanadi, keyin 8 + 8 = 16 — massivdan tashqarida, to'xtaymiz.

Yuqoridagi jadvalga qarang: 3-kun aynan shu uchta bo'lakka kiradi, boshqasiga emas.

add qiymatni almashtirmaydi, unga farq qo'shadi. "4-kun endi 9" deyish uchun eski qiymatni bilish va 9 - 2 = 7 ni qo'shish kerak. Shuning uchun amalda Fenwick yonida oddiy massiv ham saqlanadi.

Kuzating: prefix(7) uchta katakdan yig'iladi:

Diqqat: Fenwick indekslari 1 dan boshlanadi. add(0, …) cheksiz siklga tushadi: 0 & -0 = 0, i hech qachon o'smaydi. Kunlar 0 dan raqamlangan bo'lsa, chaqirishda i + 1 qiling.

Tekshirib ko'ring: prefix(6) qaysi kataklarni qo'shadi? add(5, …) qaysilarini yangilaydi (n = 8)?

5.3 Segment tree yoki Fenwick?

Fenwick oraliq minimumiga yaramaydi: prefix(r) - prefix(l - 1) hiylasi ayirish bor amallar uchungina ishlaydi. Minimumni "ayirib" bo'lmaydi. Qoida: faqat yig'indi kerak — Fenwick; boshqa narsa ham kerak — segment tree.

6. O'lchov

n ta kun va n ta amal: yarmi — tasodifiy kunni o'zgartirish, yarmi — tasodifiy oraliq yig'indisi (urug'li generator).

Avval ikki massivli yechim:

Endi daraxtlar, xuddi shu amallarda:

Oddiy massiv va prefix sum: n ikki baravar — vaqt to'rt baravarga yaqin (O(n²)). Prefix sum bu aralashmada oddiy massivdan ham sekin: uning yangilashi qolgan butun massivni qayta yozadi, oddiy massivning so'rovi esa faqat oraliqni ko'radi. Segment tree va Fenwick: ikki baravar (O(n log n)). Fenwick segment tree'dan 4–5 baravar tez — rekursiya va 4n massiv o'rniga ikkita qisqa sikl. Kattaroq n da ham: 800 000 kunda segment tree ≈ 780 ms, Fenwick ≈ 136 ms.

Maslahat: So'rovlar ko'p, o'zgarish yo'q bo'lsa — prefix sum (O(1)) hammasidan tez. O'zgarish ko'p, so'rov kam bo'lsa — oddiy massiv. Daraxtlar ikkala amal ham ko'p bo'lganda o'zini oqlaydi. Avval amallar nisbatini bilib oling.

7. Chegaraviy holatlar

• Bo'sh massiv. new SegmentTree([]) qurilmaydi (n = 0 tekshiruvi). So'rov berishdan oldin uzunlikni tekshiring.
• l > r. Bizning sum 0 qaytaradi (hamma tugun "kesishmaydi" holatiga tushadi). Bu jimgina xato bo'lishi mumkin — kirishni tekshirgan ma'qul.
• Chegaradan tashqari indeks. set(100, …) 8 kunlik daraxtda oxirgi bargni o'zgartirib yuboradi — xato xabarisiz! Ochiq API'da indeksni tekshiring.
• Manfiy qiymatlar. Yig'indi uchun muammo yo'q (qaytarilgan pul). Fenwick ham ishlaydi.
• Katta summalar. Yig'indi Number.MAX_SAFE_INTEGER (≈ 9 kvadrillion) dan oshsa, aniqlik yo'qoladi (Pul va aniq hisob-kitob). So'mda bu juda katta son, lekin tiyin bilan va ko'p yillik ma'lumotda e'tiborli bo'ling.

8. Ko'p uchraydigan xatolar

8.1 Fenwick'da 0-indeks

add(0, 5) — cheksiz sikl: i += 0. Sahifa yoki server qotib qoladi. Tuzatish: Fenwick'ga doim i + 1 bering.

8.2 Fenwick'da add ni set deb o'ylash

days.add(4, 9) 4-kunni 9 qilmaydi — 9 qo'shadi. Tuzatish: farqni (yangi - eski) bering va eski qiymatlarni alohida massivda saqlang.

8.3 Segment tree massivi 2n

Rekursiv qurilishda n ikkining darajasi bo'lmasa, indekslar 2n dan oshib ketadi va undefined bilan hisoblar NaN bo'ladi. Tuzatish: 4 * n.

8.4 Minimum daraxtida betaraf qiymat — 0

Kesishmaydigan tugun 0 qaytarsa, hamma narxlar musbat bo'lganda oraliq minimumi doim 0 chiqadi. Tuzatish: minimum uchun Infinity, maksimum uchun -Infinity.

9. Mashqlar

1-mashq (oson): Bo'laklarni toping

n = 16. prefix(13) qaysi kataklarni qo'shadi va har biri qaysi kunlarni qamraydi? add(3, …) qaysi kataklarni yangilaydi? Ishora: 13 = 1101₂.

2-mashq (o'rta): Eng arzon narx

«Bahor» har kuni ko'k choy uchun eng arzon ulgurji narxni yozadi. MinTree klassini yozing: min(l, r) — l-kundan r-kungacha eng kichik narx. Darsdagi SegmentTree dan boshlang va «Yig'indidan boshqa amallar» bo'limidagi uchta o'zgarishni qiling.

class MinTree {
  constructor(values) {
    this.n = values.length;
    this.tree = new Array(4 * this.n).fill(Infinity);
    if (this.n > 0) this.#build(values, 1, 0, this.n - 1);
  }
  #build(values, node, lo, hi) {
    if (lo === hi) {
      this.tree[node] = values[lo];
      return;
    }
    const mid = Math.floor((lo + hi) / 2);
    this.#build(values, 2 * node, lo, mid);
    this.#build(values, 2 * node + 1, mid + 1, hi);
    const left = this.tree[2 * node];
    const right = this.tree[2 * node + 1];
    this.tree[node] = Math.min(left, right);
  }
  min(l, r, node = 1, lo = 0, hi = this.n - 1) {
    if (r < lo || hi < l) return Infinity; // "betaraf" qiymat
    if (l <= lo && hi <= r) return this.tree[node];
    const mid = Math.floor((lo + hi) / 2);
    return Math.min(
      this.min(l, r, 2 * node, lo, mid),
      this.min(l, r, 2 * node + 1, mid + 1, hi),
    );
  }
}

// 8 kunlik eng arzon ko'k choy narxi (so'm)
const tea = new MinTree([5000, 4500, 5200, 4800,
  4000, 5100, 4900, 5300]);
console.log(tea.min(0, 3), tea.min(2, 6)); // 4500 4000
console.log(tea.min(5, 7)); // 4900

3-mashq (qiyin): Ikkala daraxtni oddiy massiv bilan tekshiring

kurs/mashqlar/14/44-oraliq/oraliq.test.mjs faylida darsdagi SegmentTree va Fenwick ni yozing. Eng muhim test — tasodifiy sinov: oddiy massiv bilan yonma-yon 1 000 ta tasodifiy amal (yangilash yoki so'rov) bajaring va har so'rovda uchala javob teng ekanini tekshiring. Tasodif — urug'li generator bilan (Asosiy murakkablik sinflari darsidagi makeRandom), test har safar bir xil o'tsin. Yana: bitta kun va bo'sh oraliq; manfiy qiymatlar.

// kurs/mashqlar/14/44-oraliq/oraliq.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

class SegmentTree {
  constructor(values) {
    this.n = values.length;
    this.tree = new Array(4 * this.n).fill(0); // 1 — ildiz
    if (this.n > 0) this.#build(values, 1, 0, this.n - 1);
  }
  #build(values, node, lo, hi) {
    if (lo === hi) {
      this.tree[node] = values[lo]; // barg — bitta kun
      return;
    }
    const mid = Math.floor((lo + hi) / 2);
    this.#build(values, 2 * node, lo, mid);
    this.#build(values, 2 * node + 1, mid + 1, hi);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
  sum(l, r, node = 1, lo = 0, hi = this.n - 1) {
    if (r < lo || hi < l) return 0; // kesishmaydi
    if (l <= lo && hi <= r) return this.tree[node]; // to'liq ichida
    const mid = Math.floor((lo + hi) / 2);
    return (
      this.sum(l, r, 2 * node, lo, mid) +
      this.sum(l, r, 2 * node + 1, mid + 1, hi)
    );
  }
  set(i, value, node = 1, lo = 0, hi = this.n - 1) {
    if (lo === hi) {
      this.tree[node] = value;
      return;
    }
    const mid = Math.floor((lo + hi) / 2);
    if (i <= mid) this.set(i, value, 2 * node, lo, mid);
    else this.set(i, value, 2 * node + 1, mid + 1, hi);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
}

class Fenwick {
  constructor(n) {
    this.tree = new Array(n + 1).fill(0); // 1 dan boshlanadi
  }
  add(i, delta) {
    // i-kunga delta qo'shiladi (kunlar 1 dan)
    for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
  }
  prefix(i) {
    // 1-kundan i-kungacha yig'indi
    let total = 0;
    for (; i > 0; i -= i & -i) total += this.tree[i];
    return total;
  }
  rangeSum(l, r) {
    return this.prefix(r) - this.prefix(l - 1);
  }
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

test("bitta kun va bo'sh oraliq", () => {
  const seg = new SegmentTree([7]);
  assert.equal(seg.sum(0, 0), 7);
  const fen = new Fenwick(3);
  assert.equal(fen.prefix(0), 0); // 0 kun — yig'indi 0
  assert.equal(fen.rangeSum(2, 2), 0);
});

test("manfiy qiymatlar (qaytarilgan pul)", () => {
  const values = [5, -3, 7, -2];
  const seg = new SegmentTree(values);
  const fen = new Fenwick(4);
  values.forEach((v, i) => fen.add(i + 1, v));
  assert.equal(seg.sum(1, 3), 2);
  assert.equal(fen.rangeSum(2, 4), 2); // Fenwick — 1 dan
});

test("1 000 ta tasodifiy amal — oddiy massiv bilan bir xil", () => {
  const random = makeRandom(45);
  const n = 50;
  const plain = Array.from({ length: n }, () => random() % 100);
  const seg = new SegmentTree(plain);
  const fen = new Fenwick(n);
  plain.forEach((v, i) => fen.add(i + 1, v));
  for (let k = 0; k < 1000; k++) {
    const a = random() % n;
    const b = random() % n;
    if (k % 2 === 0) {
      const value = random() % 100;
      fen.add(a + 1, value - plain[a]); // Fenwick farqni oladi
      seg.set(a, value);
      plain[a] = value;
    } else {
      const [l, r] = [Math.min(a, b), Math.max(a, b)];
      const want = plain.slice(l, r + 1).reduce((s, v) => s + v, 0);
      assert.equal(seg.sum(l, r), want);
      assert.equal(fen.rangeSum(l + 1, r + 1), want);
    }
  }
});

✔ bitta kun va bo'sh oraliq (0.8353ms)
✔ manfiy qiymatlar (qaytarilgan pul) (0.1887ms)
✔ 1 000 ta tasodifiy amal — oddiy massiv bilan bir xil (3.2908ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 91.7173

4-mashq: Amaliy tajriba — oraliq so'rovlari jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga oraliq so'rovlari uchun to'rt yechimni qo'shing: oddiy massiv, prefix sum, segment tree, Fenwick. Har biriga "qachon tanlanadi" ustuni.

| Yechim | So'rov | Yangilash | Xotira | Qachon |
|---|---|---|---|---|
| Oddiy massiv | O(n) | O(1) | O(1) | so'rov kam |
| Prefix sum | O(1) | O(n) | O(n) | o'zgarish yo'q |
| Segment tree | O(log n) | O(log n) | O(4n) | ikkalasi ko'p, min/max ham |
| Fenwick | O(log n) | O(log n) | O(n) | ikkalasi ko'p, faqat yig'indi |

git add 14/MURAKKABLIK.md 14/44-oraliq
git commit -m "14/44: segment tree va Fenwick, tasodifiy sinov"

10. Real ishda

• Analitika. "Oxirgi 30 kun ichida", "shu hafta" kabi oraliq hisoblari o'zgarib turadigan ma'lumotda — dashboard'lar ortida. Katta tizimlarda bu ish ma'lumotlar bazasi yoki maxsus vaqt qatorlari tizimlariga topshiriladi, lekin ichida o'xshash tuzilmalar ishlaydi.
• Matn muharrirlari va o'yinlar. Qatorlar balandligi o'zgarib turadigan uzun ro'yxatda "N-qator qayerda boshlanadi?" — prefiks yig'indisi, Fenwick bilan. Reyting jadvallarida "mendan yuqorida nechta o'yinchi" — ham shunday.
• Raqobatli dasturlash. Segment tree va Fenwick — olimpiada va Codeforces masalalarining asosiy vositalari. Kengaytmalari bor: oraliqni birdaniga yangilash (lazy propagation), ikki o'lchovli daraxtlar.
• Intervyu. "Range Sum Query — Mutable" (LeetCode 307) — klassik savol. Kutilgan javob: prefix sum nega yaramasligi va segment tree yoki Fenwick.

Xulosa

• O'zgaruvchan massivda oraliq so'rovlari: oddiy massiv — so'rov O(n), prefix sum — yangilash O(n); segment tree va Fenwick — ikkalasi O(log n).
• Segment tree: har tugunda oraliqning tayyor natijasi; so'rov — uch holat (kesishmaydi, to'liq ichida, qisman), yangilash — barggacha yo'l va qaytishda qayta hisoblash.
• Segment tree istalgan assotsiativ amal uchun (yig'indi, min, max); kerakli betaraf qiymatni bering.
• Fenwick: tree[i] — uzunligi i & -i bo'lgan bo'lak; ikkita sikl, 1 dan indekslar, faqat yig'indi kabi amallar; add farq qo'shadi.
• O'lchov: 80 000 aralash amal — Fenwick ≈ 8 ms, segment tree ≈ 37 ms, oddiy massiv ≈ 1,3 s, prefix sum ≈ 9,4 s.

Keyingi dars: Graf atamalari va ko'rinishlari — daraxtlardan graflarga: tugunlar istalgancha bog'lanadi, sikllar paydo bo'ladi.

Manbalar

• Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables", Software: Practice and Experience, 1994.
• cp-algorithms.com: "Segment Tree", "Fenwick Tree" — batafsil tushuntirish va kengaytmalar.
• LeetCode 307 "Range Sum Query - Mutable" — leetcode.com (sharti boshqacha, g'oyasi shu darsdagi).
• MDN: Bitwise AND (&), two's complement — developer.mozilla.org