Farqlar massivi

Farqlar massivini qanday qurish kerak

Kirish

Farqlar massivi — ko‘plab oraliq yangilanishlarni samarali qo‘llash uchun foydali usul.

$[L, R]$ segmentidagi har bir elementni o‘zgartirish o‘rniga, biz yordamchi massivda faqat bir nechta pozitsiyalarni yangilaymiz. Barcha yangilanishlar qayta ishlangandan so‘ng, prefiks yig‘indilar yordamida yakuniy massivni qayta tiklaymiz.

Bu har bir oraliq yangilanishni $O(1)$ vaqt ichida bajarishga imkon beradi.

G‘oya

Uzunligi $n$ bo‘lgan $a$ massiv berilgan bo‘lsin, uning farqlar massivi diff quyidagicha aniqlanadi:

• $diff_1 = a_1$