Prefix sum va difference array: istalgan oraliq yig'indisini O(1) da olish

Qisqacha: Prefix sum — prefix[i] = birinchi i ta elementning yig'indisi. Uni bir marta O(n) da qurasiz, keyin istalgan oraliq yig'indisi bitta ayirish: sum(l..r) = prefix[r + 1] - prefix[l] — O(1). Jadval uchun 2D prefix sum to'rtburchak yig'indisini to'rtta son bilan beradi. Difference array — teskari g'oya: oraliqqa qiymat qo'shish ikki katakda (diff[l] += x, diff[r + 1] -= x), oxirida bitta prefix o'tishi. Prefix sum va Map birga "yig'indisi aniq k bo'lgan bo'laklar sonini" manfiy sonlar bilan ham O(n) da topadi.

Bu darsda

• Prefix massivini qurasiz va q ta oraliq savoliga O(n · q) o'rniga O(n + q) da javob berasiz.
• 2D prefix sum bilan jadvaldagi istalgan to'rtburchak yig'indisini O(1) da olasiz.
• Difference array bilan ko'p bronlarni bitta o'tishda soatlarga taqsimlaysiz.
• Prefix sum va Map bilan yig'indisi berilgan songa teng bo'laklarni sanaysiz.

Oldin bilishingiz kerak: Sliding window, Map, fill va Array.from, Kodning murakkabligini hisoblash.

1. Nega bu kerak?

Yil oxiri. Jasur aka «Bahor»ning 365 kunlik tushumini oldi va savollar yog'dirdi: "Mart oyida jami qancha?", "Navro'z haftasida-chi?", "1-iyundan 15-avgustgacha?" Har savol — bitta oraliq yig'indisi. Sardor har biriga sikl yozadi: l dan r gacha qo'shish.

Bitta savol — O(n), muammo yo'q. Lekin hisobot sahifasi foydalanuvchi har sanani tanlaganda yangi savol beradi. Yuzlab foydalanuvchi, minglab savol. q ta savol — O(n · q). O'tgan darsdagi suriluvchi oyna bu yerda yordam bermaydi: savollar ketma-ket emas, istalgan joydan istalgan joygacha.

Yechim — maktabdan tanish g'oya. Kitob sahifalari raqamlangan: 120-sahifadan 150-sahifagacha nechta sahifa? Sanab chiqmaysiz — 150 − 120 + 1. Prefix sum tushumni xuddi shunday "raqamlab" qo'yadi: har kun uchun "yil boshidan shu kungacha jami". Keyin istalgan oraliq — ikki sonning ayirmasi.

2. Prefix sum

2.1 Qurish va so'rash

Prefix sum (old yig'indi) — yangi massiv: prefix[i] — birinchi i ta elementning yig'indisi. prefix[0] = 0 — "hali hech bir kun yo'q". Shu sababli prefix massivi asl massivdan bitta uzun.

Oraliq l..r yig'indisi: prefix[r + 1] — birinchi r + 1 kun, prefix[l] — birinchi l kun. Ayirsak — aynan l dan r gacha kunlar qoladi. Haftalik misolni kuzating (ikki massiv: yuqorida tushum, pastda prefix):

Qurish — bitta sikl, O(n) vaqt va O(n) xotira. Har savol — ikki o'qish va bitta ayirish, O(1). q ta savol — O(n + q).

prefix[0] = 0 nega kerak? Usiz l = 0 (oraliq boshidan) holati alohida if talab qilardi. Bitta qo'shimcha nol katak hamma savolni bitta formulaga keltiradi. Bu kichik hiyla — qorovul (sentinel) deb ataladi.

2.2 O'lchov

n kunlik tushum va n ta tasodifiy oraliq savoli (urug'li), olcha, har n alohida jarayonda:

Chap ustun: n ikki baravar — vaqt to'rt baravar. Savollar ham, ularning uzunligi ham n bilan o'sadi — O(n · q) = O(n²). Prefix ustunidagi raqamlar juda kichik va shovqinli. Kattaroq n da aniqroq ko'rinadi: 250 000 — ≈ 5 ms, 500 000 — ≈ 7,6 ms, 1 000 000 — ≈ 18 ms. Taxminan chiziqli. Million kun va million savol — 18 millisekund.

Tekshirib ko'ring: sales = [4, 1, 3, 2]. prefix massivini yozing. sum(1..3) qancha?

2.3 Oyna yoki prefix?

O'tgan darsdagi qat'iy oyna ham ketma-ket yig'indilarni O(n) da hisoblardi. Farqi:

Oxirgi qatorga e'tibor bering: prefix sum faqat ma'lumot o'zgarmasa yaxshi. Bitta kunning tushumi tuzatilsa, undan keyingi hamma prefix o'zgaradi — O(n). Ko'p yangilanish va ko'p savol aralash bo'lsa, Segment tree va Fenwick tree ikkalasini ham O(log n) da qiladi.

3. 2D prefix sum: jadvaldagi to'rtburchak

3.1 Masala

Jasur akaning tushum jadvali: qatorlar — haftalar, ustunlar — dushanba, seshanba, chorshanba, payshanba (mln so'm). Savol: "2- va 3-haftalarning seshanbadan payshanbagacha jami?" — bu jadvaldagi to'rtburchak.

          Du  Se  Cho  Pa
1-hafta    3   5    2   6
2-hafta    4   1    7   2
3-hafta    5   3    3   8

Sodda yo'l — to'rtburchak kataklarini qo'shish, O(qatorlar × ustunlar) har savolga.

3.2 G'oya: "chap-yuqori burchakdan" yig'indi

P[r][c] — chap-yuqori burchakdan (0, 0) boshlab, r ta qator va c ta ustunli to'rtburchak yig'indisi. 1D dagi kabi, nol qator va nol ustun qo'shiladi (qorovul).

Qurish formulasi: yangi katak + yuqoridagi to'rtburchak + chapdagi to'rtburchak − ikkalasida ham hisoblangan burchak. Burchak ikki marta qo'shilgani uchun bir marta ayiriladi. To'rtburchak yig'indisi ham shu mantiq bilan, to'rt son bilan olinadi:

function build2D(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  // P[r][c] — chap-yuqori r × c to'rtburchak yig'indisi
  const P = Array.from(
    { length: rows + 1 },
    () => new Array(cols + 1).fill(0),
  );
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      P[r + 1][c + 1] =
        grid[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
    }
  }
  return P;
}

function rectSum(P, r1, c1, r2, c2) {
  return P[r2 + 1][c2 + 1] - P[r1][c2 + 1]
    - P[r2 + 1][c1] + P[r1][c1];
}

const weeks = [
  [3, 5, 2, 6],
  [4, 1, 7, 2],
  [5, 3, 3, 8],
];
const P = build2D(weeks);
console.log(rectSum(P, 1, 1, 2, 3)); // 24
console.log(rectSum(P, 0, 0, 2, 3)); // 49

Birinchi savol: 2–3-haftalar (indeks 1–2), seshanba–payshanba (indeks 1–3): 1 + 7 + 2 + 3 + 3 + 8 = 24. Ikkinchisi — butun jadval. rectSum mantiqi: katta to'rtburchakdan yuqoridagi bo'lakni va chapdagi bo'lakni olib tashlaymiz; chap-yuqori burchak ikki marta olib tashlandi — uni bir marta qaytaramiz.

Qurish — O(qatorlar × ustunlar), har savol — O(1). Array.from bilan har qator alohida massiv bo'ladi (fill va Array.from). new Array(rows + 1).fill(new Array(...)) yozsangiz, hamma qator bitta massiv bo'lib qoladi — klassik tuzoq. Jadvallar bilan ishlashni Matritsa bilan ishlash darsida davom ettiramiz.

Tekshirib ko'ring: rectSum(P, 0, 0, 0, 0) nima qaytaradi va formulada qaysi P kataklari ishlatiladi?

4. Difference array: oraliqqa qo'shish

4.1 Teskari masala

Endi aksincha. Savol "oraliq yig'indisi qancha?" emas, buyruq: "oraliqqa qiymat qo'sh". «Bahor» bronlari: "4 kishi, 11 dan 13-soatgacha". Kun oxirida har soatda zalda nechta mehmon bo'lishini bilish kerak — oshpazlar sonini rejalash uchun.

Sodda yo'l — har bron uchun uning har soatiga kishilarni qo'shish: q ta bron, har biri L soat — O(q · L). Bron uzun, bronlar ko'p bo'lsa — sekin.

Difference array (farq massivi) g'oyasi: har soatda mehmonlar sonini emas, o'zgarishini yozamiz. Bron boshlangan soatda "+4", tugagan soatdan keyingisida "−4". Oraliq qancha uzun bo'lmasin — faqat ikki katak. Oxirida o'zgarishlarni chapdan o'ngga yig'sak (bu — prefix sum!), har soatdagi haqiqiy son chiqadi:

Har bron — O(1), oxirgi o'tish — O(n). Jami O(n + q). Prefix sum va difference array bir-birining teskarisi: prefix yig'adi, farq massivi ayiradi. Farq massividan prefix olsak — asl qiymatlar qaytadi.

diff massivi n + 1 uzun. Nega? Bron oxirgi soatgacha bo'lsa (to = 7), diff[to + 1] = diff[8] ga yoziladi. Bu katak hech qachon o'qilmaydi, lekin u bo'lmasa massivdan tashqariga yozilardi. Yana qorovul.

4.2 O'lchov

n soat va n ta bron (tasodifiy oraliqlar):

Sodda usul — to'rt baravar qadamlar bilan, kvadratik. Farq massivi — millisekunddan kam, 16 000 da 300 baravar tez.

Tekshirib ko'ring: 6 soatlik kunda ikkita bron: [0, 2, 3] va [1, 5, 1]. diff (7 katak) va har soatdagi mehmonlarni yozing.

5. Prefix sum + Map: yig'indisi k bo'lgan bo'laklar

5.1 Masala

Kassa har soatda sof o'zgarishni yozadi: tushum minus qaytarilgan pul. Shuning uchun sonlar manfiy ham bo'ladi: [3, -1, 2, -2, 4, -3, 1] (yuz ming so'm). Savol: nechta ketma-ket bo'lakda sof o'zgarish aniq 2 ga teng?

Suriluvchi oyna bu yerda ishlamaydi — manfiy sonlar tufayli oynani toraytirish yig'indini oshirishi mumkin. Sodda yechim — hamma bo'laklar, O(n²).

5.2 G'oya

Bo'lak l..r yig'indisi = prefix[r + 1] - prefix[l]. Biz shu ayirma k bo'lishini xohlaymiz:

prefix[r + 1] − prefix[l] = k → prefix[l] = prefix[r + 1] − k

Demak, chapdan o'ngga yurib, har joyda savol beramiz: "oldin qancha prefix joriy - k ga teng bo'lgan?" Har biri — bitta mos bo'lakning boshlanishi. Oldingi prefixlarni Map da sanab boramiz: prefix qiymati → necha marta uchragan. Bu Map bilan hisoblashning birinchi ko'rinishi — keyingi darsda bunday naqshlarni ko'p ko'ramiz.

function countSubarrays(changes, k) {
  const seen = new Map([[0, 1]]); // bo'sh boshlanish: prefix 0
  let prefix = 0;
  let count = 0;
  for (const x of changes) {
    prefix += x;
    // shu yerda tugaydigan mos bo'laklar soni
    count += seen.get(prefix - k) ?? 0;
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }
  return count;
}

console.log(countSubarrays([3, -1, 2, -2, 4, -3, 1], 2)); // 6
console.log(countSubarrays([0, 0], 0)); // 3

Birinchi misolni qo'lda yuramiz (k = 2). Har qatorda: kelgan son, joriy prefix, Map da qidirilgan qiymat (prefix − 2) va shu paytgacha topilgan bo'laklar:

Oxirgi qatorga qarang: prefix 2 oldin ikki marta uchragan edi. Demak, oxirgi soatda tugaydigan ikkita bo'lak bor: [2, -2, 4, -3, 1] va [4, -3, 1] — ikkalasining yig'indisi 2.

new Map([[0, 1]]) — prefix massividagi prefix[0] = 0 ning o'rni: "boshidan boshlangan bo'laklar" uchun. Usiz [2] va k = 2 → 0 chiqardi, to'g'ri javob 1. Ikkinchi misolda uchta bo'lak: birinchi 0, ikkinchi 0 va ikkalasi birga.

Vaqt — bitta o'tish, har qadamda Map ning O(1) amallari: O(n). Xotira — turli prefixlar soni, O(n). Manfiy sonlar muammo emas: biz hech qachon oynani toraytirmaymiz, faqat "oldin nima bo'lgan" deb so'raymiz.

Tartibga e'tibor bering: avval so'raymiz, keyin joriy prefixni qo'shamiz. Teskari qilsak, k = 0 da har prefix o'zini sanab, bo'sh bo'laklarni ham hisoblab yuboradi.

6. Chegaraviy holatlar

• Bo'sh massiv. prefix = [0] — savol bo'lmaydi. countSubarrays([], 0) → 0.
• l > r yoki chegaradan tashqari. prefix[r + 1] — undefined, natija NaN. Kiruvchi savollarni tekshiring.
• l = r. Bitta element: prefix[l + 1] - prefix[l] = sales[l]. Formula o'zgarishsiz ishlaydi.
• Katta yig'indilar. Million kun × million so'm = 10¹² — Number uchun xavfsiz (2⁵³ ≈ 9 · 10¹⁵ gacha butun sonlar aniq). Undan katta bo'lsa — BigInt (BigInt).
• Kasr sonlar. 0.1 + 0.2 xatosi prefixda to'planib boradi (Number turi ichidan). Pulni tiyin (butun son) bilan saqlang.

7. Ko'p uchraydigan xatolar

7.1 Bitta katak siljishi

prefix[r] - prefix[l] — r kuni chiqib qoladi. Tuzatish: formulani yodlang yoki 3 elementli misolda tekshiring: sum(l..r) = prefix[r + 1] - prefix[l].

7.2 Qo'riqchini unutish

prefix[0] = 0, Map([[0, 1]]), diff ning n + 1 uzunligi. Ularsiz chet holatlar xato beradi. Tuzatish: testda l = 0 va oxirgi elementgacha bo'lgan oraliqni albatta sinang.

7.3 O'zgaradigan ma'lumotga prefix

Har yangilanishdan keyin prefixni qayta qurish — O(n). Ko'p yangilanishda bu O(n · q). Tuzatish: Fenwick tree.

7.4 2D jadvalni fill bilan yasash

new Array(3).fill(new Array(4).fill(0)) — uchta qator bitta massiv. Bittasini o'zgartirsangiz, hammasi o'zgaradi (Havola semantikasi). Tuzatish: Array.from({ length: 3 }, () => new Array(4).fill(0)).

8. Mashqlar

1-mashq (oson): Prefix va farq

a = [2, 7, 1, 5]. (a) prefix ni yozing. (b) sum(1..2) ni prefix bilan toping. (c) [0, 3] oraliqqa 10 qo'shish uchun diff ning qaysi kataklari o'zgaradi?

2-mashq (o'rta): Muvozanat kuni

Besh kunlik tushum [3, 4, 9, 2, 5]. Shunday kun topingki, undan oldingi kunlar yig'indisi undan keyingi kunlar yig'indisiga teng bo'lsin (kunning o'zi hech qaysi tomonga kirmaydi). balanceDay(sales) indeksni qaytarsin, bunday kun bo'lmasa −1. O(n) vaqt, O(1) qo'shimcha xotira. Bu misolda javob 2: 3 + 4 = 7 va 2 + 5 = 7.

Ishora: avval jami yig'indini toping. Keyin chapdan yurib, left ni (oldingilar yig'indisi) yuritib boring. O'ng tomon = jami − left − joriy kun.

function balanceDay(sales) {
  let total = 0;
  for (const s of sales) total += s;
  let left = 0;
  for (let i = 0; i < sales.length; i++) {
    const right = total - left - sales[i];
    if (left === right) return i;
    left += sales[i];
  }
  return -1;
}

console.log(balanceDay([3, 4, 9, 2, 5])); // 2
console.log(balanceDay([1, 2, 3])); // -1
console.log(balanceDay([7])); // 0

3-mashq (qiyin): Prefix va farq massivi testlari

kurs/mashqlar/14/09-prefix/prefix.test.mjs faylida yozing: buildPrefix(arr), rangeSum(prefix, l, r) (noto'g'ri oraliqda RangeError tashlasin — throw), applyBookings(hours, bookings) (farq massivi bilan) va darsdagi countSubarrays. Testlar (node:test):

1. rangeSum 200 ta urug'li tasodifiy savolda sodda sikl bilan bir xil; l = 0 va r = n - 1 chetlari ham.
2. rangeSum(prefix, 3, 1) va chegaradan tashqari — RangeError.
3. applyBookings darsdagi misolda [0, 4, 6, 6, 7, 7, 5, 0]; bo'sh bronlar — hammasi 0.
4. countSubarrays 200 ta urug'li massivda (manfiylar bilan, uzunligi 0–25) sodda O(n²) yechim bilan bir xil.

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

function buildPrefix(arr) {
  const prefix = [0];
  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[i] + arr[i]);
  }
  return prefix;
}

function rangeSum(prefix, l, r) {
  const n = prefix.length - 1;
  if (!(0 <= l && l <= r && r < n)) {
    throw new RangeError(`noto'g'ri oraliq: ${l}..${r}`);
  }
  return prefix[r + 1] - prefix[l];
}

function applyBookings(hours, bookings) {
  const diff = new Array(hours + 1).fill(0);
  for (const [from, to, people] of bookings) {
    diff[from] += people;
    diff[to + 1] -= people;
  }
  const guests = [];
  let current = 0;
  for (let h = 0; h < hours; h++) {
    current += diff[h];
    guests.push(current);
  }
  return guests;
}

function countSubarrays(changes, k) {
  const seen = new Map([[0, 1]]);
  let prefix = 0;
  let count = 0;
  for (const x of changes) {
    prefix += x;
    count += seen.get(prefix - k) ?? 0;
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }
  return count;
}

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

test("rangeSum sodda sikl bilan bir xil", () => {
  const sales = Array.from({ length: 50 }, () => random() % 1000);
  const prefix = buildPrefix(sales);
  for (let k = 0; k < 200; k++) {
    const a = random() % 50;
    const b = random() % 50;
    const [l, r] = a < b ? [a, b] : [b, a];
    let slow = 0;
    for (let i = l; i <= r; i++) slow += sales[i];
    assert.equal(rangeSum(prefix, l, r), slow);
  }
  assert.equal(rangeSum(prefix, 0, 49), prefix[50]);
});

test("noto'g'ri oraliq — RangeError", () => {
  const prefix = buildPrefix([1, 2, 3, 4]);
  assert.throws(() => rangeSum(prefix, 3, 1), RangeError);
  assert.throws(() => rangeSum(prefix, 0, 4), RangeError);
});

test("applyBookings — misol va bo'sh", () => {
  const bookings = [[1, 3, 4], [2, 5, 2], [4, 6, 5]];
  const expected = [0, 4, 6, 6, 7, 7, 5, 0];
  assert.deepEqual(applyBookings(8, bookings), expected);
  assert.deepEqual(applyBookings(3, []), [0, 0, 0]);
});

test("countSubarrays sodda yechim bilan bir xil", () => {
  for (let t = 0; t < 200; t++) {
    const n = random() % 26;
    const arr = Array.from({ length: n }, () => (random() % 11) - 5);
    const k = (random() % 11) - 5;
    let slow = 0;
    for (let i = 0; i < n; i++) {
      let s = 0;
      for (let j = i; j < n; j++) if ((s += arr[j]) === k) slow++;
    }
    assert.equal(countSubarrays(arr, k), slow);
  }
});

✔ rangeSum sodda sikl bilan bir xil (2.1276ms)
✔ noto'g'ri oraliq — RangeError (0.5117ms)
✔ applyBookings — misol va bo'sh (0.8272ms)
✔ countSubarrays sodda yechim bilan bir xil (2.8264ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 121.7551

4-mashq: Amaliy tajriba — "Tayyorlash" ustuni

kurs/mashqlar/14/MURAKKABLIK.md ga bugungi yechimlarni qo'shing. Yangi narsa: prefix sum'da ikki narx bor — tayyorlash (bir marta) va savol (har safar). Ularni alohida yozing.

| Masala | Naqsh | Tayyorlash | Har savol |
|---|---|---|---|
| Oraliq yig'indisi | prefix sum | O(n) | O(1) |
| To'rtburchak yig'indisi | 2D prefix sum | O(r · c) | O(1) |
| Oraliqqa qo'shish (q ta) | difference array | O(n + q) | — |
| Yig'indisi k bo'laklar | prefix + Map | — | O(n) jami |

git add 14/MURAKKABLIK.md 14/09-prefix
git commit -m "14/09: prefix sum, farq massivi, prefix + Map"

9. Real ishda

• Hisobotlar va analitika. "Yil boshidan beri" (YTD) ko'rsatkichlari, sana oralig'i bo'yicha tushum — ko'pincha oldindan hisoblangan jamg'arma yig'indilar bilan. Bazalarda "kumulyativ yig'indi" (SUM(...) OVER (ORDER BY ...)) — aynan prefix sum (SQL — keyingi qismlarda).
• Rasm qayta ishlash. 2D prefix sum "integral image" deb ataladi — rasmning istalgan to'rtburchagidagi yorug'likni O(1) da olish uchun (yuz aniqlashning klassik usullarida ishlatilgan).
• Bron va jadval tizimlari. Mehmonxona, kinoteatr, «Bahor» zali — "har soatda nechta joy band" difference array bilan hisoblanadi.
• Intervyu. LeetCode'dagi "Range Sum Query — Immutable", "Range Sum Query 2D", "Car Pooling", "Subarray Sum Equals K", "Find Pivot Index" — bugungi besh masalaning asl nomlari.

Xulosa

• Prefix sum: bir marta O(n), keyin har oraliq yig'indisi prefix[r + 1] - prefix[l] — O(1). 16 000 savolda sodda usul 73 ms, prefix — 1 ms dan kam.
• 2D prefix sum: to'rtburchak yig'indisi to'rtta son bilan; qurishda burchak bir marta ayiriladi.
• Difference array: oraliqqa qo'shish — ikki katak, oxirida bitta prefix o'tishi. O(n + q).
• Prefix + Map: "oldin joriy - k necha marta bo'lgan?" — manfiy sonlar bilan ham O(n).
• Qo'riqchilar (prefix[0] = 0, Map([[0, 1]]), n + 1 uzun diff) chet holatlarni umumiy formulaga keltiradi.

Keyingi dars: Hash map bilan hisoblash naqshlari — chastota hisoblagichi, "ikki son yig'indisi" saralanmagan ro'yxatda, anagrammalarni guruhlash va birinchi takror.

Manbalar

• Jon Bentley, "Programming Pearls", 2-nashr, Addison-Wesley, 1999 — 8-bob (kumulyativ yig'indilar)
• Paul Viola, Michael Jones, "Rapid Object Detection using a Boosted Cascade of Simple Features", CVPR 2001 — integral image
• LeetCode masalalari: "Range Sum Query — Immutable", "Range Sum Query 2D — Immutable", "Car Pooling", "Subarray Sum Equals K", "Find Pivot Index" — leetcode.com (shartlar bu yerda o'zgartirib berilgan)