前缀和、差分
前缀和
前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和
一维
定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
const int N = 1e5 + 10;
int sum[N], a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i = 1;i <= n; i++)
{
sum[i] = sum[i - 1] + a[i];
}
二维
转移方程
s[i][j] = s[i - 1][j] + s[i][j - 1 ] + a[i] [j] - s[i - 1][j - 1]
双层for循环执行转移方程即可
差分
好课：【C++算法基础】#9前缀和与差分 图解ACM竞赛算法_哔哩哔哩_bilibili
一维
diff就是差分数组的表现形式
因为差分数组只能先修改完毕，再求出原数组的修改结果，而后构造前缀和，通过前缀和进行查询。所以叫“离线”，即：不能变修改边访问
修改
实现
输入一个n，代表接下来要输入的数据个数，
而后输入一组数据，
随后输入一个区间和一个x，要将这个区间的每个元素+x
最后输入几组两个数，代表需要输出的区间
