1. 排序算法

快速排序

时间复杂度：最好 $O(nlog(n))$ 平均 $O(nlog(n))$ 最坏 $O(n^2)$

空间复杂度：$O(log(n))$

稳定性：不稳定

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1, x = a[mid];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i ++ ; while (a[i] < x);
        do j -- ; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

归并排序

时间复杂度：$O(nlog(n))$

空间复杂度：$O(n)$

稳定性：稳定

int a[N], tmp[N], n;

void merge_sort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] < a[j]) tmp[k ++ ] = a[i ++ ];
        else tmp[k ++ ] = a[j ++ ];
    }
    while (i <= mid) tmp[k ++ ] = a[i ++ ];
    while (j <= r) tmp[k ++ ] = a[j ++ ];
    for (int i = l, k = 0; i <= r; i ++ ) a[i] = tmp[k ++ ];
}

2. 二分法

整数二分（注意考虑边界问题）

• 查找某个值

int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r >> 1;
    if (a[mid] == k) return mid;
    else if (a[mid] > k) r = mid;
    else l = mid;
}

return -1;

• 排序数组找值左边界

int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r >> 1;
    if (a[mid] >= k) r = mid;
    else l = mid + 1;
}

• 排序数组找值右边界

int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r + 1 >> 1;
    if (a[mid] <= k) l = mid;
    else r = mid - 1;
}

浮点数二分（注意精度的选择和判断条件）

double l = -10000, r = 10000;
while (r - l > 1e-8) {
    double mid = (l + r) / 2.0;
    if (mid * mid * mid >= n) r = mid;
    else l = mid;
}

3. 高精度

高精度加法

vector<int> add(vector<int> &A, vector<int> &B) {
    if (A.size() < B.size()) return add(B, A);
    vector<int> 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(1);
    return C;
}

高精度减法

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];
    return true;
}

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

高精度乘法

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

高精度除法

vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> 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;
}

4. 前缀和

数组a，前缀和数组S

一维

$S[i] = \sum_{t = 1}^{i}a[t], \sum_{t = l}^{r}a[t] = S[r] - S[l - 1]$

二维

$S[x][y] = \sum_{i = 1}^{x}\sum_{j = 1}^{y}a[i][j]$
$\sum_{x = x_{1}}^{x_{2}}\sum_{y = y_{1}}^{y_{2}}a[x][y] = S[x_{2}][y_{2}] - S[x_{1} - 1][y_{2}] - S[x_{2}][y_{1} - 1] + S[x_{1} - 1][y_{1} - 1]$

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];

5. 差分

一维

序列中[l, r]之间的每个数加上c

$a[l] += c, a[l + 1] += c, …, a[r] += c. O(n)$
$S[l] += c, S[r + 1] -= c. O(1)$

二维

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c

$a[x_{1}][y_{1}] += c, …, a[x_{2}][y_{2}] += c. O(n^2)$
$S[x_{1}][y_{1}] += c, S[x_{2} + 1][y_{1}] -= c, S[x_{1}][y_{2} + 1] -= c, S[x_{2} + 1][y_{2} + 1] += c. O(1)$

6. 双指针

用两个指针维护具有某种性质的区间，没有固定套路和公式，具体问题具体分析

7. 位运算

8. 离散化

稀疏区间到稠密区间的映射，遍历原始区间很耗时

有负数坐标的存在，原始区间无法求前缀和

最坏情况下，输入数据中不同的点有$n + 2m$个，所以数组要开3倍的范围防止越界

步骤

// 数组排序去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

1. 存储所有操作 $O(n)$
2. 数轴坐标去重并排序，目的是构造下标映射 $O(nlog(n))$
3. 添加操作 $O(n)$
4. 前缀和 $O(n)$
5. 查询操作 $O(n)$

9. 区间合并

void merge(vector<PII> &segs) {
    sort(segs.begin(), segs.end());
    vector<PII> ret;
    int st = -2e9, ed = -2e9;
    for (int i= 0; i < segs.size(); i++) {
        if (segs[i].first > ed) {
            if (ed != -2e9) ret.push_back({st, ed});
            st = segs[i].first, ed = segs[i].second;
        } else {
            ed = max(ed, segs[i].second);
        }
    }
    if (ed != -2e9) ret.push_back({st, ed});
    segs = ret;
}