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