arvindf232's blog

(Rolling) Range Sum Query of binomial coefficients
By arvindf232, history, 22 hours ago, In English

This is absolutely a well known trick. However, I simply find no blogs discussing this (with a searchable title), so I hope to fill this gap in references.

This blog consists of one sentence

Range Sum Query of binomial coefficients is almost doable in a MO's rolling manner.

The details are easy to derive on your own. For the completness of the blog, they are included:

Consider the following simple range sum query problem on binomial coefficients

Problem Find the following sums , $$$B(l,r,n)=\sum_{i=l}^{r}\binom{n}{i}$$$, evaluated mod a prime.

It seems like there is no simple and realistic way to answer a single query any faster than $$$O(r-l+1)$$$. (Though as pointed out by Elegia, you could do something in $$$O(\sqrt{r-l})$$$ times log factors using some P-recursive concepts).

However, in many situations where we need to answer many such queries (e.g. as part of a counting process), the values of $$$B(l,r,n)$$$ we need change only slightly and predictably. In this case, we can answer all queries in essentially amortized $$$O(1)$$$.

Almost-Solution Suppose we know the answer to $$$B(l,r,n)$$$, then we can obtain answer to $$$B(l',r',n')$$$ in $$$O(|l-l'|+|r-r'|+|n-n'|)$$$ time.

Implementation Changing l,r are easy. For convenience:

  • l++: subtract by $$$\binom{n}{l}$$$
  • l--: add by $$$\binom{n}{l-1}$$$
  • r++: add by $$$\binom{n}{r+1}$$$
  • r--: subtract by $$$\binom{n}{r}$$$

To change n, we see that

$$$2B(l,r,n)=\binom{n}{l}+\binom{n}{r}+\sum_{i=l}^{r-1}(\binom{n}{i}+\binom{n}{i+1})$$$

$$$=\binom{n}{l}+\binom{n}{r}+\sum_{i=l}^{r-1}(\binom{n+1}{i+1})$$$

$$$=\binom{n}{l}+\binom{n}{r}+B(l+1,r,n+1)$$$

$$$=\binom{n}{l}+\binom{n}{r}-\binom{n+1}{l}+B(l,r,n+1)$$$

This gives the equation for both incrementing n and decrementing n.

Remark We could also implement and analyse using only using binomial prefix, $$$B(r,n)=\sum_{i=0}^{r}\binom{n}{i}$$$. I decided to analyse the ranges version since it isn't difficult.

Remark The formula given has no special cases. Make sure that for non-negative integers $$$n$$$, $$$\binom{n}{i}=0$$$ for $$$i\not\in[0,n]$$$, and calculating them do not result in out-of-bounds error. In particular, it works for $$$n \leq 0 $$$ for the standard definition (allowing negative $$$n$$$). However, if we assumed $$$\binom{n}{i}=0$$$ for negative $$$n$$$ in implementation then this would be wrong because of $$$\binom{0}{0}=1=\binom{-1}{-1} +\binom{-1}{0}$$$.

Exercise It is now easy to answer online queries of $$$B(l,r,n')$$$ with $$$O(n\sqrt{n})$$$ precalculation and $$$O(\sqrt{n})$$$ per query, for queries with $$$n'\leq n$$$.

solution

Edit: Thanks to jeroenodb for these extra references

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

»
20 hours ago, # |
  Vote: I like it -38 Vote: I do not like it

arvindf232 what's the benefit of these things? Elegia

→ Reply
»
20 hours ago, # |
  Vote: I like it +14 Vote: I do not like it

Nice trick!

What is the $$$O(\sqrt{r - l} \cdot polylog(n)$$$ per query solution by Elegia?

→ Reply
»
11 hours ago, # |
  Vote: I like it +14 Vote: I do not like it

You should also add 1450H2 - Multithreading (Hard Version) as a reference.

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a doubt, since its a recursive function now, Can we somehow use Matrix exponentiation to optimize its calculation further ?

→ Reply
  • »
    »
    5 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    Matrix exponentiation is only possible if all terms and transitions are linear. While a matrix can easily keep track of $$$l,r,n,B(l,r,n)$$$, it cannot simulate the $$$\binom{n}{l}$$$ etc or perform any types of multiplications needed to maintain the binomial coefficients added/subtracted. (So at least, integer matrix would not be enough)

    → Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This can be done in $$$O(n\log^2 n)$$$. orzdevinwang's blog

→ Reply
  • »
    »
    5 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Also, the generalized version (as mentioned by -is-this-dp) where you calculate the prefix products of a sequence of polynomial matrices can be solved similarly.

    → Reply
  • »
    »
    5 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain what it meant by “D and C polynomial mod” in the last paragraph making it $$$O(n log^2)$$$? I cannot quite see why modding $$$x—n$$$ helps since it is same as a typical multipoint evaluation.

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

      Basically, we want to calculate $$$\prod_{i=1}^l M_i(n)$$$ for multiple $$$(n,l)$$$ queries, where $$$M_i(x)$$$ is a polynomial matrix of constant size and degree.

      Build a segment tree, for a query $$$(n,l)$$$ we put it onto the leaf representing $$$l$$$. Then do a DFS solve(l,r,P), which means we are currently at a node representing $$$[l,r]$$$, and $$$\prod_{i=1}^{l-1} M_i=P$$$. Pre-calculate the product of $$$M$$$ for each interval on the segment tree takes $$$O(n\log^2 n)$$$ time, and each time we pass the argument $$$P$$$ down, we only need to pass $$$P\bmod \prod(x-n_i)$$$, where $$$n_i$$$ are the parameters of the queries inside the subtree. It's clear that the sum of degrees of all $$$P$$$ is $$$O(n\log n)$$$.

      → Reply