# Prefix sum 2-dimensional

**URL:** <https://forum.olinfo.it/t/prefix-sum-2-dimensional/3835>\
**Category:** Algoritmi\
**Created:** [17 Agosto 2014, 3:00pm UTC](https://forum.olinfo.it/t/prefix-sum-2-dimensional/3835 "2014-08-17T15:00:17Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [17 Agosto 2014, 3:00pm UTC](https://forum.olinfo.it/t/prefix-sum-2-dimensional/3835/1 "2014-08-17T15:00:17Z")

</div>

Avete idee su come effettuare una prefix sum in un array 2x2 ? Cioè avendo un array 2x2 in cui ogni cella ha un valore, se voglio avere la somma dei valori contenuti in un sottoarray(sottomatrice) dell’originale, riesco ad ottenerlo in tempo constante.&nbsp;

---

<div class="post-metadata">

**Author:** ![Mazzetto](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/87869e/32.png) [@Mazzetto](https://forum.olinfo.it/u/Mazzetto)\
**Post date:** [17 Agosto 2014, 3:08pm UTC](https://forum.olinfo.it/t/prefix-sum-2-dimensional/3835/2 "2014-08-17T15:08:17Z")

</div>

Per una matrice C NxM qualunque l’idea è la seguente:

ti computi per ogni casella il valore S(x,y), cioè la somma dei valori della sottomatrice dalla casella (0,0) alla casella (x,y).

Per computare S(x,y) in maniera veloce si può notare che, con i dovuti accorgimenti nei casi limite (cioè quanto x = 0 o y = 0), che S(x,y) = S(x-1, y) + S(x,y-1) - S(x-1,y-1) + C(x,y).

Una volta computato S, si può trovare la somma di una sottomatrice qualunque in tempo costante (prova a disegnare).&nbsp;

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [17 Agosto 2014, 4:17pm UTC](https://forum.olinfo.it/t/prefix-sum-2-dimensional/3835/3 "2014-08-17T16:17:28Z")

</div>

Prova a risolvere raisins utilizzando anche questo metodo 😉

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [18 Agosto 2014, 8:30am UTC](https://forum.olinfo.it/t/prefix-sum-2-dimensional/3835/4 "2014-08-18T08:30:18Z")

</div>

Si adesso proverò di capirlo, poi lo volevo usare proprio per velocizzare raisins! Grazie 🙂