Разбор

Розглянемо префіксні суми $pre{f}_1,pre{f}_2,\dots ,pre{f}_n$ ($pre{f}_i=a_1+a_2+\dots +a_i$). Легко помітити, що коли ми робимо операцію з позицією $i$, то префіксні суми $pre{f}_{i-1}$ та $pre{f}_i$ міняються місцями, а інші не змінюютьс