# Prefix sum modification

So, yesterday there was a contest named code sprint there, and they asked this question. I couldn’t solve it, can anyone help me how to restore the original array from a prefix array.

Hoping you meant prefix sum.

This is quite simple.
Say your Array is [a_1,\ a_2,\ a_3,\ a_4,\ ...,\ a_{n-1}]. Its prefix Sum will be:
[s_1, s_2, s_3, ..., s_{n-1}], where
s_1 = a_1,
s_2 = a_1 + a_2
s_3 = a_1 + a_2 + a_3 and so on.
So, to get the original array,
a_1 = s_1
a_2 = s_2 - s_1
a_3 = s_3 - s_2

a_{n-1} = s_{n-1} - s_{n-2}

Then, we process the queries in reverse order.
We will process the last query first. But Instead of adding, we will perform a subtraction query. This has to be done in \log N time. So, you might want to use Segment tree or fenwick tree( also called BIT).

2 Likes

Hi, I am sharing an alternate approach since the constraints look like O(N+Q) is needed

1. Notation

1. A_0: Original Array
2. A_1: Array after segment updates
3. A_2: Prefix Sum Array
4. Using 1-based array indexing to explain. i.e. first element is a_{1}, last is a_{N}

2. Getting A_1 from A_2

• First, using a linear traversal of the prefix sum array, one can easily find the individual elements
• a_1=s_1
• a_i=s_i-s_{i-1} for i>1

3. Getting A_0 from A_1

• Recall that we had added some element I to Q segments [L,R]. So we need to subtract the same now to get our answer
• Let’s remember that we need to subtract I starting at index L and add it back starting at index R+1 using an update array. This information should be sufficient to recreate the array.
• For each query, update_L= update_L-I
• Similarly, update_{R+1}=update_{R+1}+I
• Lastly, traverse the update array to propagate the addition/subtraction effects. i.e. update_{i+1}=update_{i+1}+update_{i}. After this update, we will get everything we need to update for each index. (why?)
• Reconstructing the original array from A_1 is as simple as a_i+update_i