算法复习（二分+离散化+快速排序+归并排序+树状数组）

一、二分算法

二分算法，堪称算法世界中的高效查找利器，其核心思想在于利用数据的有序性，通过不断将查找区间减半，快速定位目标元素或满足特定条件的位置。

1. 普通二分

普通二分适用于在有序数组中查找特定元素的位置。我们可以进一步细分需求，如查找满足条件的最左边的数的下标，或者最右边的数的下标。以代码中的 find1 和 find2 函数为例：

cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n, m;int find1(int x) {int l = 0, r = n + 1;int ans = 0;while (l <= r) {int mid = (l + r) >> 1;if (a[mid] > x) {r = mid - 1;}else if (a[mid] == x) {ans = mid;r = mid - 1;}else if (a[mid] < x) {l = mid + 1;}}return ans;
}
int find2(int x) {int l = 0, r = n + 1;int ans = 0;while (l <= r) {int mid = (l + r) >> 1;if (a[mid] > x) {r = mid - 1;}else if (a[mid] == x) {ans = mid;l = mid + 1;}else if (a[mid] < x) {l = mid + 1;}}return ans;
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}while (m--) {int tmp;cin >> tmp;cout << find1(tmp) - 1 << ' ' << find2(tmp) - 1 << endl;}return 0;
}

在 find1 函数中，当找到与 x 相等的元素时，我们继续将右边界 r 调整为 mid - 1，目的是持续向左查找，确保最终得到的是最左边的符合条件的下标。而 find2 函数在找到相等元素后，将左边界 l 调整为 mid + 1，以此向右查找最右边的符合条件的下标。这种技巧在处理重复元素较多的数组时，能够精准定位特定位置，为后续的数据处理提供极大便利。

2. 数值二分

数值二分则是将二分思想应用于数值求解领域。例如，在求一个浮点数的三次方根问题中，我们利用数值二分的方法可以高效且准确地得到结果。

cpp

#include<iostream>
#include<iomanip>
using namespace std;
double n, l, r, mid;
double q(double a) {return a * a * a;
}
int main() {cin >> n;l = -10000, r = 10000;while (r - l >= 1e-7) {mid = (l + r) / 2;if (q(mid) >= n) r = mid;else l = mid;}cout << fixed << setprecision(6) << l;return 0;
}

我们先确定一个可能包含三次方根的区间 [l, r]，在这个例子中，由于任何实数的三次方根都在 -10000 到 10000 这个较大范围之内（对于一般竞赛和实际应用场景中的数值而言），我们以此作为初始区间。然后，通过不断缩小区间范围，当区间长度小于一定精度（这里是 1e-7）时，我们认为此时的左边界 l 就是所求三次方根的近似值。数值二分在处理这类数值逼近问题时，展现出了极高的效率和稳定性，相较于暴力枚举等方法，大大减少了计算量。

二、排序算法

排序算法是数据处理领域的核心算法之一，它能够将无序的数据整理成有序的序列，为后续的数据查找、统计、分析等操作奠定基础。

1. 快速排序

快速排序凭借其高效的性能，在众多排序算法中脱颖而出，广泛应用于各类场景。它基于分治策略，通过选择一个基准值，将数组划分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值，然后递归地对左右两部分进行排序。

cpp

#include<bits/stdc++.h>
using namespace std;const int N = 1000010;
int a[N];
int n;
void q(int l, int r) {if (l >= r) return;if (l + 1 == r) {if (a[l] > a[r]) swap(a[l], a[r]);return;}int i = l - 1, j = r + 1;int x = a[(i + j) >> 1];while (i <= j) {do i++; while (a[i] < x);do j--; while (a[j] > x);if (i < j) swap(a[i], a[j]);}q(l, j); q(j + 1, r); // 注意这里是j
}
int main() {cin >> n;for (int i = 0; i < n; i++) scanf("%d", &a[i]);q(0, n - 1);for (int i = 0; i < n; i++) printf("%d ", a[i]);
}

在代码中，我们选取数组中间位置的元素作为基准值 x。通过两个指针 i 和 j 从数组两端向中间移动，将小于基准值的元素交换到左边，大于基准值的元素交换到右边。当 i 和 j 相遇时，数组就被划分成了符合条件的两部分。随后，递归地对这两部分继续进行快速排序，直至整个数组有序。快速排序的平均时间复杂度为 O(nlogn)，在数据量较大时表现出色。

快排的延展：第 k 个数
基于快速排序的思想，我们可以进一步拓展其应用，快速找出数组中第 k 小的数。这在很多需要统计特定位置元素的场景中非常实用。

cpp

#include<bits/stdc++.h>
using namespace std;const int N = 1000010;
int a[N];
int n;int q(int l, int r, int k) {if (l >= r) return a[l];if (l + 1 == r) {if (a[l] > a[r]) swap(a[l], a[r]);if (k == 1) return a[l];return a[r];}int i = l - 1, j = r + 1;int x = a[(i + j) >> 1];while (i <= j) {do i++; while (a[i] < x);do j--; while (a[j] > x);if (i < j) swap(a[i], a[j]);}int len = j - l + 1;if (k <= len) // 注意这里的是k<=len,而不是k<=j+1return q(l, j, k);return q(j + 1, r, k - len);
}
int main() {int k;cin >> n >> k;for (int i = 0; i < n; i++) scanf("%d", &a[i]);cout << q(0, n - 1, k);}

在每次划分后，我们计算左半部分的长度 len。如果 k 小于等于 len，说明第 k 小的数在左半部分，我们递归在左半部分查找；否则，在右半部分查找，并且将 k 调整为 k - len，因为我们已经排除了左半部分的 len 个数。这种方法避免了对整个数组进行完全排序，大大提高了查找特定位置元素的效率。

2. 归并排序

归并排序同样是一种基于分治思想的排序算法，它将数组逐步分解为较小的子数组，分别进行排序后，再将这些有序的子数组合并成一个最终的有序数组。

cpp

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int tmp[N];
void merge_sort(int l, int r) {if (l >= r) return;int mid = l + r >> 1;merge_sort(l, mid); merge_sort(mid + 1, r);int ls = l, rs = mid + 1; int tmpread = 0;while (ls <= mid && rs <= r) {if (a[ls] < a[rs]) tmp[tmpread++] = a[ls++];else tmp[tmpread++] = a[rs++];}while (ls <= mid) tmp[tmpread++] = a[ls++];while (rs <= r) tmp[tmpread++] = a[rs++];for (int i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];
}
int main() {cin >> n;for (int i = 0; i < n; i++) cin >> a[i];merge_sort(0, n - 1);for (int i = 0; i < n; i++) cout << a[i] << ' ';return 0;
}

在代码实现中，我们首先将数组递归地划分为左右两部分，直到子数组长度为 1（此时子数组自然有序）。然后，在合并阶段，通过两个指针 ls 和 rs 分别指向左右两个子数组的起始位置，比较并将较小的元素依次放入临时数组 tmp 中。当其中一个子数组遍历完后，将另一个子数组剩余的元素直接复制到 tmp 中。最后，将 tmp 数组中的元素复制回原数组 a，完成一次合并。归并排序的时间复杂度稳定在 O(nlogn)，并且它是一种稳定的排序算法，即在排序过程中，相同元素的相对顺序保持不变。

归并排序的延伸：逆序对
归并排序的思想还可以巧妙地用于统计数组中的逆序对数量。逆序对在许多算法问题中有着重要的应用，比如计算数组的无序程度等。

cpp

#include <iostream>
using namespace std;const long long N = 1000010;
long long n;
long long a[N];
long long tmp[N];// 归并排序并统计逆序对数量
long long merge_sort(long long l, long long r) {if (l >= r) return 0;if (l + 1 == r) {if (a[l] > a[r]) {swap(a[l], a[r]);return 1;}return 0;}long long mid = l + r >> 1;long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);long long ls = l, rs = mid + 1, tmpread = 0;while (ls <= mid && rs <= r) {if (a[ls] <= a[rs]) {tmp[tmpread++] = a[ls++];}else {// 当 a[ls] > a[rs] 时，a[ls...mid] 都与 a[rs] 构成逆序对res += mid - ls + 1;tmp[tmpread++] = a[rs++];}}while (ls <= mid) tmp[tmpread++] = a[ls++];while (rs <= r) tmp[tmpread++] = a[rs++];for (long long i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];return res;
}int main() {cin >> n;for (long long i = 0; i < n; i++) cin >> a[i];cout << merge_sort(0, n - 1);return 0;
}

在合并过程中，当我们发现 a[ls] > a[rs] 时，这意味着 a[ls] 到 a[mid] 这 mid - ls + 1 个元素都与 a[rs] 构成逆序对，因此将这个数量累加到结果 res 中。通过递归地进行归并排序和逆序对统计，我们能够高效地得到整个数组的逆序对数量。

三、区间和

在处理区间和相关问题时，离散化与树状数组的组合是一种非常强大的解决方案。当我们面对无限长数轴上的区间操作，或者数据范围过大导致直接存储和处理困难时，离散化可以将实际用到的数据映射到一个较小的连续空间中，大大减少内存占用和计算量。而树状数组则为快速更新和查询区间和提供了便利。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 树状数组类
class FenwickTree {
private:vector<int> tree;int n;// 计算最低位的 1 所代表的值int lowbit(int x) {return x & -x;}public:FenwickTree(int size) : n(size), tree(size + 1, 0) {}// 单点更新操作void update(int idx, int val) {while (idx <= n) {tree[idx] += val;idx += lowbit(idx);}}// 前缀和查询操作int query(int idx) {int res = 0;while (idx > 0) {res += tree[idx];idx -= lowbit(idx);}return res;}
};// 二分查找数值对应的下标
int find(int x, const vector<int>& a) {int l = 0, r = a.size() - 1;while (l < r) {int mid = l + r >> 1;if (a[mid] >= x) r = mid;else l = mid + 1;}// 如果 x 小于最小的位置，返回 0if (a[l] > x) return 0;return l + 1; // 下标从 1 开始
}int main() {int n, m;cin >> n >> m;vector<pair<int, int>> operations(n);vector<pair<int, int>> queries(m);vector<int> all_positions;// 读取操作并记录所有位置for (int i = 0; i < n; ++i) {cin >> operations[i].first >> operations[i].second;all_positions.push_back(operations[i].first);}// 读取查询并记录所有位置for (int i = 0; i < m; ++i) {cin >> queries[i].first >> queries[i].second;all_positions.push_back(queries[i].first);all_positions.push_back(queries[i].second);}// 离散化处理sort(all_positions.begin(), all_positions.end());all_positions.erase(unique(all_positions.begin(), all_positions.end()), all_positions.end());// 创建树状数组FenwickTree fenwickTree(all_positions.size());// 执行操作for (const auto& op : operations) {int idx = find(op.first, all_positions);fenwickTree.update(idx, op.second);}// 处理查询for (const auto& query : queries) {int l = find(query.first, all_positions);int r = find(query.second, all_positions);int result = fenwickTree.query(r) - fenwickTree.query(l - 1);cout << result << endl;}return 0;
}