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

Edit: Thanks to jeroenodb for these extra references

• ARC061D Link and Um_nik's video on it: Link
• 2030G2 - The Destruction of the Universe (Hard Version)
• 1450H2 - Multithreading (Hard Version) -- thanks to A_G
• ARC190B Link