Efficientent Algorithm for Fast Response to Subarray Requests
I ran into a query related issue the other day, but I can't seem to solve it.
Given an array with N integers and a positive integer M, you have to answer Q queries. Each request is characterized as (i, j), where i and j are each array index. In each request, you must answer how many pairs (r, s) exist in such a way that
- i <= r <= s <= j
- the sum of array elements with indices in [r, s] is divisible by M.
Limitations:
N <= 50,000
Q <= 50,000
M <= 100
I have a dynamic programming solution that processes every request (r, s) in O (N ^ 2), but that is not fast enough. Is there a better solution? I have some ideas with Mo algorithm or segment trees but I can't get it.
source to share
-
Calculate the prefix sums of the original array (assuming it is based on 1) for each
i = 1..N
. Equivalence and for any two indices and which means that the sum of elements in the array indexes in divided into (and we need to calculate the number of equivalences in the range). The complexity of this step is .
Sum[r]
Sum[s]
r
s
r < s
[r+1, s]
M
O(N)
-
Pre-calculate the array
Count
for eachi = 1..N, j = 0..M-1
: stores the number of times when (where ) is equal . Time complexity of this step .
Count[i][j]
Sum[len]
len <= i
j
O(N*M)
-
For each request, the
(i, j)
answer will be: For each possible value of the remainder, we find - the number of times when equal in the interval . Then add to the result the number of all possible pairs of interval boundaries that . Complexity of time: for each request.
k
D(k)
Sum[len]
k
[i, j]
D(k)
D(k)*(D(k)-1)/2
O(M)
Complexity : O(N) + O(N*M) + O(Q*M) = O((Q+N)*M)
which would be ok for the given constraints.
source to share
First of all, note that for any subarray (r, s)
that is summed with a multiple M
:
sum(r, s) == sum(i, s) - sum(i, r - 1) == (qa * M + ra) - (qb * M + rb)
where ra
and is rb
less than M
and is greater than or equal to 0
(i.e., the corresponding remainders after division by M
).
Now sum(r, s)
divisible by M
, so the remainder 0
after division by M
. Therefore:
ra == rb
If we calculate all the remains after dividing the sum of sub-arrays (i, i)
, (i, i + 1)
..., (i, j)
on M
both r1
, r2
..., rj
then save the expense of all of them in an array of R
sizes M
, so R[k]
- is the number of residues equal k
, then:
R[0] == the number of subarrays starting at i that are divisible by M
and for any k >= 0
and k < M
such that R[k] > 1
can be considered R[k]
choose 2
:
(R[k] * (R[k] - 1)) / 2
not beginning with i
, which are divisible by M
.
Creating and summing all of these values gives us an O (N + M) answer for each request (r, s)
.
source to share