prefix sum

what’ s prefix sum?

Consider the follow situation:

“Give you lots of query about the sum of segment [l,r],and without modifying”

how to solve this?

In brute force,we caculate from left to right every time,in the most worst case,we will use O(N) time according to every query.

But we can slove this problem,in a more elegant ways,

We can use a prefix sum array ,we can call it sum,it doesn’t matter,the sum[i] means that

$sum[i]=a[1]+a[2]+…+a[i]​$,

therefore,

$ a[l]+a[l+1]+…+a[r] == sum[r]-sum[l-1]​$

In this way , we can answer the above query in O(1) time.

Another Problem

There is an another problem,

“At the beginning,the value of array are all zero,give you lots of operations which add a number $x_i​$ to segment[$ l_i ​$,$ r_i ​$], and after that,query the value of a[i] “

It’s obviously that we have a brute way,but as above,we also can be in a elegant mananer to solve this problem by using prefix sum.

In every operation,plus $x_i$ to segement $[l_i,r_i]$,instead of add $x_i$ to every element in the segment,we can just add $xi$ to $a{l_i}$,and add $-xi$ to $a{r_i+1}​$,and in the last query,just scanning from left to right,and caculate the prefix sum.

that’s to say,for every operation,Instead of

for i in range(l,r+1):
	add(a_i,value)

we can use this

add(a_l,value)
add(a_{r+1},-value)

In query,just scanning from left to right,and caculate prefix sum.

$ modify:O(1),query:O(N) ​$

Why this solution is right?

It uses the idea of difference(差分),consider that:

the origin array:

$a_0,a_1,a_2,…,al,a{l+1},…a_{r-1},a_r,…,a_n$ $(a_0=0)$

add x to segment[l:r],the array will be like:

$a_0,a_1,a_2,….al+x,a{l+1}+x,…a_{r-1}+x,a_r+x,…,a_n$

if we use $ ai -a{i-1} $,we can get a new array $ b_i $

the origin array:

$a_1-a_0,a_2-a_1,a_3-a_2,al-a{l-1},a{l+1}-a{l},…,a{r}-a{r-1},a_{r+1}-a_r,…,an-a{n-1}$

after operation:

$a_1-a_0,a_2-a_1,a_3-a_2,al-a{l-1}+x,a{l+1}-a{l},…,a{r}-a{r-1},a_{r+1}-a_r-x,…,an-a{n-1}$

we can draw a conclusion,if we add x to segment[l:r] in a,

we can do it by $add(al,x) ,add(a{r+1},-x)$ to b instead

if we want to get the value of $a_t​$,just caculate the prefix sum of $b_1+…+b_t​$.