文章目录

• 高精度        
  • 高精度加法
  • 高精度减法
  • 高精度乘法
  • 高精度除法
• 前缀和
  • 一维前缀和
  • 二维前缀和
• 差分
  • 一维差分
  • 二维差分

一、高精度

1.高精度加法

// C = A + B, A >= 0, B >= 0
vector add(vector &A, vector &B)
{if (A.size() < B.size()) return add(B, A);vector C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}

2.高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector sub(vector &A, vector &B)
{vector C;for (int i = 0, t = 0; i < A.size(); i ++ ){t = A[i] - t;if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

3.高精度乘法

// C = A * b, A >= 0, b >= 0
vector mul(vector &A, int b)
{vector C;int t = 0;for (int i = 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();return C;
}

4.高精度除法

// A / b = C ... r, A >= 0, b > 0
vector div(vector &A, int b, int &r)
{vector C;r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

二、前缀和

1.一维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

#includeusing namespace std;const int N = 100010;int n, m;
int a[N], s[N];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)s[i] = s[i - 1] + a[i];while (m--){int l, r;cin >> l >> r;cout << s[r] - s[l - 1] << endl;}return 0;
}

2.二维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

#includeusing namespace std;const int N = 1010;int n, m, q;
int a[N][N], s[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m >> q;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];while (q--) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]<

#includeusing namespace std;const int N = 100010;int n, m;
int a[N], b[N];void insert(int l, int r, int c)
{b[l] += c;b[r + 1] -= c;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)insert(i, i, a[i]);while (m--) {int l, r, c;cin >> l >> r >> c;insert(l, r, c);}for (int i = 1; i <= n; i++)b[i] += b[i - 1];for (int i = 1; i <= n; i++)cout << b[i] << " ";return 0;
}

#includeusing namespace std;const int N = 1010;int n, m,q;
int a[N][N], b[N][N];void insert(int x1, int y1, int x2, int y2,int c)
{b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m>>q;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)insert(i, j, i, j, a[i][j]);while (q--) {int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cout << b[i][j] << " ";return 0;
}