前缀和

1. Def. 某数组前若干数的和

   设一数组$a$，$s[1]=a[1]$，$s[2]=a[1]+a[2]$，

   $s[n]=a[1]+a[2]+…+a[n-1]+a[n]$.

2. 用此方法求区间$[l,r]$的和

   $$ s_{lr}=s[r]-s[l-1] $$

3. 相较于$for$循环求若干数的和，前缀和这一算法能将时间复杂度由$O(n)$降为$O(1)$。

   前缀和属于优化类算法。

差分

1. Def. 是这个数与前一个数的差

   设一数组$a$，则有

   $$ d[1]=a[1]\d[2]=a[2]-a[1]\d[3]=a[3]-a[2]\d[n]=a[n]-a[n-1] $$

   ******注意！！！$a[0]=0$.

2. 差分多用于对区间$[l,r]$中的每一项都进行相同的修改（加减）

   例题可见 Hydro B0409或洛谷P2367。

   对于普通的数组，使某区间内的每一项进行相同加减，需要用$for$循环，做如下操作

   $$ a[l]+=c\a[l+1]+=c\……\O(n) $$

   对于差分数组，只需要做

   $$ d[l]+=c\d[r+1]-=c\O(1) $$

   故与前缀和一样，是优化类算法。同时，差分算法是前缀和的逆运算。

3. 根据差分数列反求出修改后的原数列

   可使用如下代码

   for(int i=1;i<=n;i++)
       {
           d[i]+=d[i-1];
           cout<<d[i]<<" ";
       }
   

   我好像也不太理解 但是先背着吧

二维前缀和

1. 即针对二维的$a$数组的前缀和操作。

   偷懒直接上图。

   

   

2. 尺取法（Two pointers）

   1. 无法评述。参见例题。

   P1147 连续自然数和

   题目描述

   对一个给定的正整数 $M$，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 $M$。

   例子：$1998+1999+2000+2001+2002 = 10000$，所以从 $1998$ 到 $2002$ 的一个自然数段为 $M=10000$ 的一个解。

   输入格式

   包含一个整数的单独一行给出 $M$ 的值（$10 \le M \le 2,000,000$）。

   输出格式

   每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

   样例 #1

   样例输入 #1

   10000
   

   样例输出 #1

   18 142
   297 328
   388 412
   1998 2002
   

   AC Code

   //20230707 @ Hydro.ac
   //尺取法
   #include<bits/stdc++.h>
   using namespace std;
   int m,sum=0;
   int main()
   {
       cin>>m;
       for(int l=1,r=1;r<m;r++)
       {
           sum+=r;
           while(sum>m)//如果总和大于m
           {
               sum-=l;//在总和中删掉起点
               l++;
           }
           if(sum==m)
               cout<<l<<" "<<r<<endl;
       }
       return 0;
   }