Yahia_Emara's blog

[PROBLEM] The subarray sum function
By Yahia_Emara, 3 years ago, In English

We have an array $$$A$$$ of length $$$N$$$, let's define a function $$$f$$$ which takes 3 parameters $$$(L,R,K)$$$ such that $$$(1 ≤ L ≤ R ≤ N)$$$, $$$f(L,R,0)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (A_i)$$$, and $$$f(L,R,K)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (\sum\limits_{j=i}^R (f(i,j,K-1)))$$$

We are going to call the function $$$f$$$ $$$Q$$$ Times, What is the best time complexity you can achieve?

My best time complexity to solve this is using DP with 2D prefix sum to calculate the answer for every possible tuple (i,j,k) using previous tuples in O(n^2 * maxK), Unfortunately...That's not efficient

However, I have found an Extra Greedy+Math+Inclusion-Exclusion-Principle O(n) pre-processing and O(1) per query solution for $$$(K=0)$$$ or $$$(K=1)$$$, but that's all I could do

Any comments on this function?

Note : since the value of this function may grow rapidly beyond the 64-bit integer datatype limit, you are asked to calculate its value modulo $$$10^9+7$$$

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I only think $$$f(1,r,k)=\sum\limits_{j=1}^r \binom{r-i+k}{k}\binom{j+k-1}{j-1}\times a_j$$$ ?

so if u only have one k, u can use MTT to optimize it?

I'm not good at CP,forgive me if I'm wrong.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One way to look at this is that we are going to choose all possible k-nested sub-arrays, and then sum the values in the inner sub-array.

As the first comment suggested, we can then go for each element and count how many times it will appear.

The formula for that can then reduce to something like this: we want to place $$$k$$$ pointers in the range $$$[1, i]$$$ and another k pointers in the range $$$[i, n]$$$

Each pointer in the first range corresponds to some left border of some subarray, same for the second range.

We can use stars and bars for that we have $$$k$$$-indistinguishable pointers and $$$i$$$ places to put them so $$${{i + k - 1} \choose k}$$$

For the right-border pointers, we have $$${{r - i + k } \choose k}$$$

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice idea, this will solve all queries in $$$O(n)$$$ So the time complexity would be $$$O(max(N,maxK)*log(max(N,maxK)$$$ for preprocessing factorilas and their modular inverse, and $$$O(NQ)$$$ or $$$O(n)$$$ per query
    This has an advantage over the algorithm above in the blog for large $$$K,N$$$and Relativly Small $$$Q$$$
    But could there be a better answer?

    → Reply