Hello everyone This problem was one of the problems in the ECPC qualifications, and I couldn't think of an efficient way to solve it.
We are given an array a of n integer, and an integer k. Next, we will have q queries, each query has L R. We need to answer the following question for each query: How many subarrays in the range L to R (inclusive) where sum of each subarray is equal to K?
To be honset I couldn't find a good solution to this problem. So I would appreciate your help.
Input:
n = 10 k = 5
a = {2 3 0 0 0 2 3 1 1 0}
7
1 2
1 3
1 7
1 10
2 7
2 6
3 8
Output:
1
2
9
11
5
1
4
Auto comment: topic has been updated by MrPrince22 (previous revision, new revision, compare).
Why all the downvotes?
You didn't mention some important facts about the problem. First of all, it has multiple test cases. Another crucial given is that "sum of n and sum of q over all t don't exceed 3e4" (Actually, this is a key to the problem and makes it easy) Thus it can be solved in O(t*n*q), but hints and code provided will first discuss a pure brute force approach O(t*q*n^2) to provide a clearer explanation then optimize with frequency map to store the frequency of prefix sums (Binary search tree not a hash as there might be anti-hash tests) (would add a log n factor but almost a constant)
Goal is to find the count of sub-arrays bound by L and R whose sum = k
It's crystal clear, the necessity to do prefix sum (pre) to access the sum(l, r) of any sub-array in O(1) later in queries. Input O(n), cumulative sum O(n)
A naive brute force (but useful for later validating the soln) would be an n^2 per query iterating over all possible sub-arrays (all l and all r). and check if pre[r] minus pre[l-1] = k , then increment the count, let it be var (ans) and print it at the end.
The earlier approach sure time limits. So to optimize, use a frequency map, iterate over possible ends (r <= R) of sub-array with given range and use a complement idea with frequency map to count number of left ends that satisfy sub-array sum = k. Key is prefix sum and value is the frequency count of such left ends.
pre[L-1] is the prefix sum of all elements before index L, it represents an empty sub-array as we are searching within (L, R), so its freq = 1.
Since pre[r] minus pre[l-1] = k, rearranging we get pre[r] minus k = pre[l-1] Moving r(every possible end of a sub-array) to the right ( <= R ), update the frequency of prefix sum (how many times each sum appears iterating over the right ends r of the subarrays). This info is then used to check if there is a left end l such that the sum of subarray from l to r = k if pre[r] minus k >= 0, then update the frequency count by number of left ends satisfying sum from l to r = k , so ans += freq[pre[r]-k]
To better relate the explanation above, implementation