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