高精度/前缀和/差分

模板：

//存储方式
string a, b;//a = "123456"
vector<int> A, B;//A = [6,5,4,3,2,1]
for(int i = a.size() - 1; i >= 0; ++ i) A.push_back(a[i] - '0');
for(int i = b.size() - 1; i >= 0; ++ i) B.push_back(b[i] - '0');

//加法
vector<int> add(vector<int> &A, vector<int> &B){
	vector<int> C;
	int t = 0;
	for(int i = 0; i < A.size() || i < B.size(); ++ i){
		if(i < A.size()) t += A[i]; //t = A[i] + B[i];
		if(i < B.size()) t += B[i];
		C.push_back(t % 10);
		t /= 10;
	}
	if(t) C.push_back(1);
	return C;
}
//逆序输出
for(int i = C.size() - 1; i >= 0; -- i) cout << C[i];

模板：

//判断是否有A > B
//注意不能直接用字符串比较a,b的大小
bool cmp(vector<int> &A, vector<int> &B){
	if(A.size() != B.size()) return A.size() > B.size();
	for(int i = A.size() - 1; i >= 0; ++ i)
		if(A[i] != B[i]) return A[i] > B[i];
}

//减法，要保证A > B
vector<int> sub(vector<int> &A, vector<int> &B){
	vector<int> C;
	for(int i = 0, t = 0; i < A.size(); ++ i){
		t = A[i] - t;
		if(i < B.size()) t -= B[i]; //t = A[i] - B[i] - t
		C.push_back((t + 10) % 10);
		if(t < 0) t = 1;
		else t = 0;
	}
	//删除前导零
	while(C.size() > 1 && C.back() == 0) C.pop_back();
}
//输出
if(cmp(A, B)){
	auto C = sub(A, B);
	for(int i = C.size() - 1; i >= 0; -- i) cout << C[i];
}else if(a == b) cout << 0;
}else{
	auto C = sub(B, A); //交换位置
	for(int i = C.size() - 1; i >= 0; -- i) cout << C[i];
}

模板：

string a;
int b;
vector<int> A;
for(int i = a.size() - 1; i >= 0; -- i) A.push_back(a[i] - '0');
//乘法
vector<int> mul(vector<int> &A, vector<int> &B){
	vector<int> C;
	for(int i = 0, t = 0; i < A.size() || t; ++ i){
		if(i < A.size()) t += A[i] * b;
		C.push_back(t % 10);
		t /= 10;
	}
	while(C.size() > 1 && C.back() == 0) C.pop_back();//去前导零（b==0时）
	return C;
}

模板：

vector<int> div(vector<int> &A, int b, int &r){//r是余数，C存储商
	vector<int> C;
	r = 0;
	for(int i = A.size() - 1; i >= 0; -- i){//从高位开始算
		r = r * 10 + A[i];
		C.push_back(r % b);
		t /= b;
	}
	reverse(C.begin(), C.end());
	while(C.size() > 1 && C.back() == 0) C.pop_back();
	return C;
}

模板：

//初始化
for(int i = 1; i <= n; ++ i) s[i] = s[i - 1] + a[i];
//求和
cout << s[r] - s[l - 1];

模板：

//初始化
for(int i = 1; i <= n; ++ i)
	for(int j = 1; j <= m; ++ j)
		s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
//区间求和 左上角（a, b） 右下角（c, d）
cout << s[c][d] - s[a - 1][d] - s[c][b - 1] + s[a - 1][b - 1];

模板：

void add(int l, int r, int c){ //在区间[l, r] 上加上c
	b[l] += c;
	b[r + 1] -= c;
}
//差分数组初始化，初始化就相当于在[i, i] 区间上加上a[i]
//所以初始化就与区间修改操作统一了
for(int i = 1; i <= n; ++ i) add(i, i, a[i]);

//差分数组初始化
for(int i = 1; i <= n; ++ i) b[i] = a[i] - a[i - 1];

//求原数组,直接利用b数组
for(int i = 1; i <= n; ++ i) b[i] += b[i - 1];

模板：

//在以(x1, y1)为右上角(x2, y2)为左上角的矩形区域加上c
void add(int x1, int y1, int x2, int y2, int c){
	d[x1][y1] += c;
	d[x2 + 1][y1] -= c;
	d[x1][y2 + 1] -= c;
	d[x2 + 1][y2 + 1] += c;
}
//求原数组
for(int i = 1; i <= n; ++ i)
	for(int j = 1; j <= m; ++ j)
		d[i][j] += d[i - 1][j] + d[i][j - 1] + d[i - 1][j - 1];