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 $n$ bo‘lgan $a$ massivi bor. Biz pref yordamchi massivini quramiz, bunda pref[i] birinchi i ta elementning yig‘indisini saqlaydi.

Rekurrent formula:

• $pref_i = pref_{i-1} + a_i$