Prefix sum modification

help
,
1

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.

2

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
3

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

4. Final Comments

  1. Getting Elements from Prefix/Suffix Array can be obtained by traversing in forward/reverse order in O(N)
  2. 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.
3 Likes
4

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]

1 Like
5

Hey, this is good info. Thanks for sharing.