Массиви фарқиятҳо

Чӣ гуна массиви фарқиятро сохтан мумкин аст

Муқаддима

Як массиви фарқиятҳо як усули муфид барои татбиқи самараноки бисёр навсозиҳои диапазонӣ мебошад.

Ба ҷои тағйир додани ҳар як унсур дар як сегмент $[L, R]$, мо танҳо чанд мавқеъро дар як массиви ёрирасон навсозӣ мекунем. Пас аз коркарди ҳамаи навсозиҳо, мо массиви ниҳоиро бо истифода аз ҷамъҳои префиксӣ аз нав месозем.

Ин боис мешавад, ки ҳар як навсозии диапазонӣ дар вақти $O(1)$ иҷро шавад.

Идея

Бо дода шудани массиви $a$ бо дарозии $n$, мо массиви фарқиятҳои онро diff чунин муайян мекунем:

• $diff_1 = a_1$