Ҷамъҳои пешоянд

Чӣ тавр ҷамъҳои префиксиро сохтан мумкин аст

Муқаддима

Ҷамъҳои префиксӣ яке аз техникаҳои асоситарин дар барномасозии рақобатӣ мебошанд. Онҳо ба мо кӯмак мекунанд, ки дархостҳои диапазониро самаранок ҷавоб диҳем, маълумоти муфидро пешакӣ ҳисоб кунем ва бисёр ғояҳои brute-force-ро ба ҳалли зуд табдил диҳем.

Ғояи асосӣ содда аст: ба ҷои аз нав ҳисоб кардани ҷамъҳо барои ҳар як дархост, мо як бор арзишҳои ҷамъшавандаро месозем ва ҳар вақте лозим шавад, онҳоро дубора истифода мебарем.

Ғоя

Фарз мекунем, ки мо массиви $a$ бо дарозии $n$ дорем. Мо массиви ёрирасони pref месозем, ки дар он pref[i] ҷамъбасти аввалин i элементро нигоҳ медорад.

Рекурренсия чунин аст:

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