算法

1. 高精度
   JAVA(大整数类)和python(无限范围)不需要,先偷懒了之后再补^ . ^
2. 前缀和
   O(1)解决区间和
   一维)
   S[i]=S[i-1]+a[i]
   求和S[r]-S[l-1] ※l-1切记切记
   二维)
   S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j]
   求和S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1]
3. 差分
   0(1)解决整个区间改变相同值问题 ※insert函数的构造
   一维)insert(l,r,c)
   b[l]+=c b[r+1]-=c
   二维)insert(x1,y1,x2,y2,c)
   b[x1][y1]+=c
   b[x2+1][y1]-=c
   b[x1][y2+1]-=c
   b[x2+1][y2+1]+=c

小技巧与知识

• 前缀和中下标全部从1开始循环，避免边界条件
• const int N=xxx; int A[N] 命名多个数组时方便

今日模板算法默写框架

一维前缀和
S[i]
l-r区间和

二维前缀和
S[i, j]
(x1,y1)-(x2,y2)区间和

一维差分
void insert(int l, int r, int c)
{
}

二维差分
void insert(int x1, int y1, int x2, int y2, int c)
{
}

去长春看cba啦嘿嘿