yangi

Prefix Sum patterini O’zbek tilida

Prefix Sum patterini O’zbek tilida

Prefix Sum bu massivlar bilan ishlashda juda foydali texnika bo'lib, u bizga massiv ichidagi subarray(oraliq) yig'indilarini tez hisoblash imkonini beradi.

Oddiy yondashuvda har safar oraliq yig'indini hisoblash O(n) vaqt oladi. Prefix Sum yordamida esa buni O(1) vaqt ichida bajarish mumkin.

Prefix Sum nima?

Prefix sum bu yangi massiv bo'lib, har bir indexgacha bo'lgan elementlar yig'indisini saqlaydi.

Masalan, agar bizda quyidagi massiv bo'lsa:

nums = [1, 2, 3, 4, 5]
prefix = [1, 3, 6, 10, 15]

Bu yerda:

  • prefix[0] = 1
  • prefix[1] = 1 + 2 = 3
  • prefix[2] = 1 + 2 + 3 = 6

Prefix Sum nima uchun ishlatiladi?

Oldindan hisoblash(preprocessing) va oraliq yig'indi(range query) va boshqa masalalarda juda qo'l keladi, misol uchun bizga index 1 dan 3 gacha bo'lgan elementlar yig'indisi kerak bo'lsa:

2 + 3 + 4 = 9sum(1, 3) = prefix[3] - prefix[0]

Bu bizga O(1) vaqt ichida natijani beradi.

Prefix Sum massivini yaratish

Avval biz prefix sum massivni yaratib olamiz.

function buildPrefixSum(nums) {
  let n = nums.length
  let prefix = new Array(n)
  prefix[0] = nums[0]

  for (let i = 1; i < n; i++) {
     prefix[i] = prefix[i - 1] + nums[i]
  }
  return prefix
}

Izoh

  • prefix[i] bu 0 dan i gacha bo'lgan barcha elementlar yig'indisi
  • Loop faqat bir marta ishlaydi
  • Big O(n) chunki massiv bo'ylab bir marta yuriladi

Bu qadam faqat bir marta bajariladi.

Oraliq yig'indini olish

Endi eng muhim qism. Prefix sum tayyor bo'lgach, istalgan oraliq yig'indini juda tez olish mumkin.

function getSum(prefix, left, right) {
  if (left !== 0) {
    return prefix[right] - prefix[left - 1]
  }
  return prefix[right]
}

Bu formula qanday ishlaydi?

  • prefix[right] bu 0 dan right gacha bo'lgan yig'indi
  • prefix[left - 1] ni ayirish orqali bizga kerak bo'lmagan qism olib tashlanadi
  • O(1) chunki faqat ikki qiymat ustida amal bajariladi

Misol:

nums = [1, 2, 3, 4, 5]
prefix = [1, 3, 6, 10, 15]

getSum(prefix, 1, 3)
= prefix[3] - prefix[0]
= 10 - 1
= 9

To'liq kod:

function buildPrefixSum(nums) {
 let n = nums.length
 let prefix = new Array(n)
  prefix[0] = nums[0]

 for (let i = 1; i < n; i++) {
  prefix[i] = prefix[i - 1] + nums[i]
  }
 return prefix
}

function getSum(prefix, left, right) {
 if (left !== 0) {
     return prefix[right] - prefix[left - 1]
 }
 return prefix[right]
}

let nums = [1, 2, 3, 4, 5]
let prefix = buildPrefixSum(nums)

console.log(getSum(prefix, 1, 3)) // 2 + 3 + 4 = 9

Prefix Sum qanday masalalarda qo'llaniladi?

  • Ko'p marotaba oraliq yig'indilar so'raladigan muammolar.
  • Prefix sum + HashMap yordamida O(n) yechim.
  • Binary massivlarda teng 0 va 1 larni topish uchun.
  • Modulo bilan birga ishlatiladi.

Xulosa

Prefix Sum bu juda kuchli va oddiy pattern:

  • Oldindan hisoblash orqali vaqtni tejaydi
  • Ko'plab array muammolarini osonlashtiradi
  • LeetCode uchun majburiy bilimlardan biri

Agar siz DSA ni endi o'rganayotgan bo'lsangiz, Prefix Sum ni yaxshi tushunish keyingi mavzular uchun mustahkam asos bo'ladi.


 Aziz - Texnoman foydalanuvchisi

Muallif haqida

Aziz


Qiziq bo‘ladi:


Birinchi bo‘ling!

Iltimos, fikr bildirish uchun saytga kiring yoki ro‘yxatdan o‘ting!