3.前缀和与差分

发表于 分类于 ， 本文字数： 203

前缀和与差分

前缀和

给定一个序列，定义pre[i] = pre[i-1] +a[i]

可求区间[l,r]的和：pre[r] - pre[l-1]

可求区间的[l,r]的异或和: pre[r]^pre[l-1]

二维前缀和

根据容器原理推导得到：

定义：

1
pre[i][j] = pre[i-1][j]+pre[i][j-1]=pre[i-1][j-1]+a[i][j],pre[i][j]表示的是（i，j)右下角的一个子矩形

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏