Static Prefix Sums

Question 1

Given A[1, n] of integers, we would like to support
* Sum(i) = prefix sums from 1 to i
* RangeSum(i, j) = prefix sums from i to j

O(1) time solution

Answer 1

Store an array S of prefix sums.
~~~
S[i] = Sum(i)
RangeSum(i, j) = Sum(j) - Sum(i-1)
~~~

In C++ std::partial_sum(A.begin(), A.end(), S)

Question 2

Ilya and Queries
Given a (binary) string S[1, n] consisting only of A’s and B’s and a set of Q queries. Each query(i, j) has to report the number of positions i <= k <= j such that S[k] = S[k+1]

Answer 2

Build a binary vector B[1, n] such that B[i] = 1 iff S[i] = S[i+1], 0 otherwise
Prefix sums on B to answer to the query in O(1) time. RangeSum(i,j) also on B.

Θ(n + q)

Question 3

Little Girl and Maximum
Given A[1, n] and a set Q of q queries. A query is RangeSum(i, j).
Permute halves in A in order to maximize the sum of the results of queries in Q.

Answer 3

Figure out which index would be most important, saying which has maximum overlap count. Then just greedily assign the largest value to the index having the largest overlap count and so on.

Compute array F[1, n] such that
F[i] = number of times the position i is included in the queries
Greedly assign elements of A to elements of F: sort F and sort A and assign F[i] with A[i].

Trivial solution to compute F (Θ(qn) time):
* set F[i] = 0, for any i
* For any query (i, j) in Q, increase F[k] by one, for k in [i, j]

Faster solution to compute F (Θ(qlogq + n) time) by usign sweep line technique:
* Sort queries endpoints
* Scan endpoints from left to right and keep a counter which counts # of active queries

Fastest solution to compute F (Θ(q + n) time):
* Use a vector V to keep track of queries so that F will be the prefix sums of V.
* For q = query(i, j), we have V[i] += 1 and V[j+1] -= 1 (subtract to compensate). So from F[i] to F[j] we have an increase of 1. Up to F[i-1] everything is unchanged. From F[j-1] everything is unchanged because we compensate by decreasing by 1 V[j+1]

Sorting takes O(nlogn). Overall time complexity: compute F + sorting

Question 4

Number of ways
Given A[1, n] count the number of ways we can split A in 3 parts so that the sum of the parts are the same.

Answer 4

First thing first, sum all the values. If the total sum ArraySum is not a multiple of 3 the result is 0.

• For every prefix of A[1, i] such that the sum is equal to ArraySum/3. Result += C[i+1] where C[i+1] is the number of ways we can split A[i+1, n] in TWO parts of sum ArraySum/3 each.

How to compute C. Use a vector B and do suffix sums on it:
* B[j] = 1 iff the sum A[j, n] = ArraySum/3, 0 otherwise
* C[i+1] = suffix sum of B[i+2, n]

Θ(n) time