前缀和是一种重要的预处理,能大大降低查询的时间复杂度。
常见的有一维数组和二维数组的前缀和,设 a 为原数组,b 为前缀和数组

一维数组

定义

基础知识 - 图1

递推公式

基础知识 - 图2

二维数组

定义

基础知识 - 图3

递推公式

基础知识 - 图4