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).

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

**1. Notation**

- A_0: Original Array
- A_1: Array after segment updates
- A_2: Prefix Sum Array
- 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

**4. Final Comments**

- Getting Elements from Prefix/Suffix Array can be obtained by traversing in forward/reverse order in O(N)
- Segment Tree is overkill when we only need to update and not worry about multiple get queries. As you know, it will give O(Q log(Q)) for Q queries. Here we have only Q updates and 1 get at the end, so we can do that with interval endpoint lazy updates in O(Q). Just like if there was 1 update and Q get queries, you could actually update all points in the interval [L,R] directly. Segment tree is designed to handle the mix of those efficiently, not either alone.

Oh, I used 1 based indexing and made this mistake

Thanks for spotting it.

Edit: It should have been [a_1,\ a_2,\ a_3,\dots,\ a_n]

Hey, this is good info. Thanks for sharing.