组合数与莫队——组合数前缀和

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133559588

用莫队求组合数是一种常见套路

莫队求 $S(n,m)=\sum_{i=0}^m\binom n i$

$S(n,m+1)$ 直接做个差，然后就相当于加上 $\binom n {i+1}$

求 $S(n+1,m)$ 会麻烦点，我们需要对 $S(n,m)$ 和 $S(n,m+1)$ 相加，合并后通过上一个来表示