Na čo je to dobré?

Keď už máme vypočítané prefixové súčty pre našu postupnosť (označme ich $s_0, s_1, \dots, s_n$), dokážeme rýchlo vypočítať súčet ľubovoľnej časti tejto postupnosti.

Ak by sme napríklad chceli súčet úseku od $L$ po $R$ (vrátane oboch koncov), stačí nám jednoducho vypočítať: $s_{R+1} - s_L$.

Prečo to funguje? Rozpíšme si, čo vlastne znamená $s_L$ a $s_{R+1}$:

  • $s_L = p_1 + \dots + p_{L-1}$
  • $s_{R+1} = p_1 + \dots + p_L + \dots + p_R$

Čiže, rozdiel $s_{R+1} - s_L$ nám dá presne to, čo sme hľadali: $p_L + p_{L+1} + \dots + p_R$.

Ak by sme sa pýtali na polootvorený interval (čiže vrátane L, ale bez R), výpočet je ešte jednoduchší: $s_R - s_L$.