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] = 1prefix[1] = 1 + 2 = 3prefix[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]bu0danigacha 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]bu0danrightgacha bo'lgan yig'indiprefix[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.
Birinchi bo‘ling!