Prefiks yig‘indilar
Prefiks yig‘indilarni qanday qurish kerak
Kirish
Prefiks yig‘indilar raqobatbardosh dasturlashdagi eng asosiy texnikalardan biridir. Ular bizga oraliq so‘rovlariga samarali javob berish, foydali ma’lumotlarni oldindan hisoblash va ko‘plab brute-force g‘oyalarni tez yechimlarga aylantirishga yordam beradi.
Asosiy g‘oya oddiy: har bir so‘rov uchun yig‘indilarni qayta hisoblash o‘rniga, biz bir marta kumulyativ qiymatlarni quramiz va kerak bo‘lganda ularni qayta ishlatamiz.
G‘oya
Faraz qilaylik, bizda uzunligi bo‘lgan massivi bor. Biz pref yordamchi massivini quramiz, bunda pref[i] birinchi i ta elementning yig‘indisini saqlaydi.
Rekurrent formula: