4027 字
20 分钟
分治算法详解：从CSP-S到IOI
2026-01-21
技术
算法
/
分治
/
二分
/
CDQ
/
FFT
/
OI
/
CSP
/
IOI

分治算法详解：从CSP-S到IOI#

分治算法是算法竞赛中最重要的思想之一，从基础的二分查找到高级的CDQ分治、点分治，贯穿整个OI/ACM生涯。本文将系统讲解分治算法的各个方面。

一、分治思想基础#

1.1 什么是分治#

分治（Divide and Conquer） 是一种算法设计范式，其核心思想是：

  • 分解（Divide）：将原问题分解为若干个规模较小的子问题
  • 解决（Conquer）：递归地求解各个子问题
  • 合并（Combine）：将子问题的解合并为原问题的解

1.2 分治算法的特征#

  1. 子问题独立性：子问题之间相互独立，不重叠
  2. 最优子结构：原问题的最优解包含子问题的最优解
  3. 递归结构：问题可以递归分解

1.3 时间复杂度分析#

分治算法的时间复杂度通常可以用递推式表示：

T(n) = aT(n/b) + f(n)

其中：

  • a 是子问题个数
  • n/b 是子问题规模
  • f(n) 是分解与合并的时间

根据 主定理（Master Theorem）：

  • 若 f(n) = O(n^(log_b(a)-ε))，则 T(n) = Θ(n^(log_b(a)))
  • 若 f(n) = Θ(n^(log_b(a)))，则 T(n) = Θ(n^(log_b(a)) * log(n))
  • 若 f(n) = Ω(n^(log_b(a)+ε))，则 T(n) = Θ(f(n))

二、归并排序与逆序对#

2.1 归并排序#

归并排序是分治思想的经典应用。

void merge_sort(int arr[], int l, int r, int temp[]) {
    if (l >= r) return;


    int mid = (l + r) / 2;
    merge_sort(arr, l, mid, temp);
    merge_sort(arr, mid + 1, r, temp);


    // 合并两个有序数组
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];


    for (int i = l; i <= r; i++) {
        arr[i] = temp[i];
    }
}

时间复杂度：T(n) = 2T(n/2) + O(n) = O(n log n) 空间复杂度：O(n)

2.2 逆序对问题#

逆序对是指序列中满足 i < j 但 a[i] > a[j] 的数对 (i, j)。

利用归并排序可以在 O(n log n) 时间内统计逆序对数量：

long long merge_and_count(int arr[], int l, int r, int temp[]) {
    if (l >= r) return 0;


    int mid = (l + r) / 2;
    long long count = 0;


    count += merge_and_count(arr, l, mid, temp);
    count += merge_and_count(arr, mid + 1, r, temp);


    // 合并时统计跨越中点的逆序对
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i + 1);  // 关键：统计逆序对
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];


    for (int i = l; i <= r; i++) {
        arr[i] = temp[i];
    }


    return count;
}

三、快速排序与快速选择#

3.1 快速排序#

快速排序通过选择枢轴（pivot）将数组分为两部分。

int partition(int arr[], int l, int r) {
    int pivot = arr[r];
    int i = l - 1;


    for (int j = l; j < r; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[r]);
    return i + 1;
}


void quick_sort(int arr[], int l, int r) {
    if (l >= r) return;


    int p = partition(arr, l, r);
    quick_sort(arr, l, p - 1);
    quick_sort(arr, p + 1, r);
}

平均时间复杂度：O(n log n) 最坏时间复杂度：O(n²)（可通过随机化避免）

3.2 快速选择（第K小元素）#

快速选择算法可以在平均 O(n) 时间内找到第k小的元素。

int quick_select(int arr[], int l, int r, int k) {
    if (l == r) return arr[l];


    int p = partition(arr, l, r);
    int cnt = p - l + 1;  // 左侧元素个数


    if (k == cnt) {
        return arr[p];
    } else if (k < cnt) {
        return quick_select(arr, l, p - 1, k);
    } else {
        return quick_select(arr, p + 1, r, k - cnt);
    }
}

四、二分查找及其变种#

4.1 基础二分查找#

int binary_search(int arr[], int n, int target) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;
}

4.2 查找第一个/最后一个位置#

// 查找第一个 >= target 的位置
int lower_bound(int arr[], int n, int target) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] < target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}


// 查找第一个 > target 的位置
int upper_bound(int arr[], int n, int target) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] <= target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

五、整数二分与实数二分#

5.1 整数二分模板#

// 模板1：找满足条件的最小值
int binary_search_min(int l, int r) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}


// 模板2：找满足条件的最大值
int binary_search_max(int l, int r) {
    while (l < r) {
        int mid = l + (r - l + 1) / 2;  // 注意这里要+1
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

5.2 实数二分#

double binary_search_real(double l, double r) {
    const double eps = 1e-8;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return l;
}


// 或者固定迭代次数
double binary_search_real_iter(double l, double r) {
    for (int i = 0; i < 100; i++) {  // 100次足够精确
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return l;
}

六、二分答案#

二分答案是一种重要的算法技巧，适用于”最大化最小值”或”最小化最大值”问题。

6.1 经典例题：最小化最大值#

问题：有n本书，m个人抄写，每个人抄写连续的几本，求最小化最大抄写量。

#include <bits/stdc++.h>
using namespace std;


int n, m;
int books[505];


// 检查是否可以在最大抄写量为maxPages时完成
bool check(int maxPages) {
    int people = 1, current = 0;
    for (int i = 0; i < n; i++) {
        if (books[i] > maxPages) return false;
        if (current + books[i] > maxPages) {
            people++;
            current = books[i];
            if (people > m) return false;
        } else {
            current += books[i];
        }
    }
    return true;
}


int main() {
    cin >> n >> m;
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        cin >> books[i];
        r += books[i];
        l = max(l, books[i]);
    }


    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }


    cout << l << endl;
    return 0;
}

七、CDQ分治#

CDQ分治是陈启峰提出的一种分治算法，主要用于解决动态问题和多维偏序问题。

7.1 三维偏序问题#

问题：给定n个三元组(a, b, c)，统计每个三元组被多少个三元组”支配”（即存在三元组(x, y, z)满足x≤a, y≤b, z≤c）。

#include <bits/stdc++.h>
using namespace std;


const int MAXN = 100005;


struct Point {
    int a, b, c;
    int ans, cnt;  // ans: 被支配次数, cnt: 相同点数量
    int id;
} p[MAXN], tmp[MAXN];


int n, k;
int tree[MAXN * 2];
int result[MAXN];


bool cmp_a(const Point& x, const Point& y) {
    if (x.a != y.a) return x.a < y.a;
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}


bool cmp_b(const Point& x, const Point& y) {
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}


void add(int x, int val) {
    for (; x <= k; x += x & -x) {
        tree[x] += val;
    }
}


int query(int x) {
    int res = 0;
    for (; x; x -= x & -x) {
        res += tree[x];
    }
    return res;
}


void cdq(int l, int r) {
    if (l >= r) return;


    int mid = (l + r) / 2;
    cdq(l, mid);
    cdq(mid + 1, r);


    // 归并排序，按b排序
    sort(p + l, p + mid + 1, cmp_b);
    sort(p + mid + 1, p + r + 1, cmp_b);


    int j = l;
    for (int i = mid + 1; i <= r; i++) {
        while (j <= mid && p[j].b <= p[i].b) {
            add(p[j].c, p[j].cnt);
            j++;
        }
        p[i].ans += query(p[i].c);
    }


    // 清空树状数组
    for (int i = l; i < j; i++) {
        add(p[i].c, -p[i].cnt);
    }
}


int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].a >> p[i].b >> p[i].c;
        p[i].cnt = 1;
        p[i].id = i;
    }


    sort(p + 1, p + n + 1, cmp_a);


    // 去重
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (i > 1 && p[i].a == p[i-1].a && p[i].b == p[i-1].b && p[i].c == p[i-1].c) {
            p[tot].cnt++;
        } else {
            p[++tot] = p[i];
        }
    }


    cdq(1, tot);


    for (int i = 1; i <= tot; i++) {
        result[p[i].ans + p[i].cnt - 1] += p[i].cnt;
    }


    for (int i = 0; i < n; i++) {
        cout << result[i] << "\n";
    }


    return 0;
}

7.2 CDQ优化动态规划#

CDQ分治可以优化某些DP转移，将O(n²)优化到O(n log n)。

八、点分治#

点分治是处理树上路径问题的强大工具。

8.1 树上路径统计#

问题：给定一棵树和距离K，求距离不超过K的点对数量。

#include <bits/stdc++.h>
using namespace std;


const int MAXN = 10005;


vector<pair<int, int>> adj[MAXN];  // {邻接点, 边权}
bool vis[MAXN];
int sz[MAXN], maxSz[MAXN];
int n, k;
long long ans = 0;


void getSize(int u, int fa) {
    sz[u] = 1;
    maxSz[u] = 0;
    for (auto [v, w] : adj[u]) {
        if (v == fa || vis[v]) continue;
        getSize(v, u);
        sz[u] += sz[v];
        maxSz[u] = max(maxSz[u], sz[v]);
    }
}


int getRoot(int u, int fa, int total) {
    maxSz[u] = total - sz[u];
    int root = u;
    for (auto [v, w] : adj[u]) {
        if (v == fa || vis[v]) continue;
        int subRoot = getRoot(v, u, total);
        if (maxSz[subRoot] < maxSz[root]) {
            root = subRoot;
        }
    }
    return root;
}


vector<int> dist;


void getDist(int u, int fa, int d) {
    dist.push_back(d);
    for (auto [v, w] : adj[u]) {
        if (v == fa || vis[v]) continue;
        getDist(v, u, d + w);
    }
}


long long calc(int u, int initDist) {
    dist.clear();
    getDist(u, -1, initDist);
    sort(dist.begin(), dist.end());


    long long res = 0;
    int l = 0, r = dist.size() - 1;
    while (l < r) {
        if (dist[l] + dist[r] <= k) {
            res += r - l;
            l++;
        } else {
            r--;
        }
    }
    return res;
}


void solve(int u) {
    getSize(u, -1);
    int root = getRoot(u, -1, sz[u]);


    vis[root] = true;
    ans += calc(root, 0);


    for (auto [v, w] : adj[root]) {
        if (vis[v]) continue;
        ans -= calc(v, w);
        solve(v);
    }
}


int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cin >> k;


    solve(1);
    cout << ans << endl;


    return 0;
}

时间复杂度：O(n log² n)

九、线段树分治#

线段树分治用于处理带时间维度的问题，特别是动态图问题。

9.1 动态图连通性#

#include <bits/stdc++.h>
using namespace std;


const int MAXN = 100005;


struct DSU {
    int fa[MAXN], sz[MAXN];
    stack<pair<int, int>> stk;


    void init(int n) {
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }


    int find(int x) {
        return fa[x] == x ? x : find(fa[x]);
    }


    bool merge(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        stk.push({y, sz[x]});
        fa[y] = x;
        sz[x] += sz[y];
        return true;
    }


    void undo() {
        auto [y, oldSz] = stk.top();
        stk.pop();
        int x = fa[y];
        sz[x] = oldSz;
        fa[y] = y;
    }
};


struct Edge {
    int u, v, l, r;  // 边(u,v)在时间[l,r)内存在
};


vector<Edge> edges;
vector<int> queries[MAXN * 4];
DSU dsu;


void insert(int o, int l, int r, int ql, int qr, int id) {
    if (ql <= l && r <= qr) {
        queries[o].push_back(id);
        return;
    }
    int mid = (l + r) / 2;
    if (ql < mid) insert(o * 2, l, mid, ql, qr, id);
    if (qr > mid) insert(o * 2 + 1, mid, r, ql, qr, id);
}


void solve(int o, int l, int r) {
    int cnt = 0;
    for (int id : queries[o]) {
        if (dsu.merge(edges[id].u, edges[id].v)) {
            cnt++;
        }
    }


    if (l + 1 == r) {
        // 处理时刻l的查询
        // ...
    } else {
        int mid = (l + r) / 2;
        solve(o * 2, l, mid);
        solve(o * 2 + 1, mid, r);
    }


    // 撤销操作
    for (int i = 0; i < cnt; i++) {
        dsu.undo();
    }
}

十、FFT与NTT#

快速傅里叶变换（FFT）和数论变换（NTT）用于快速计算多项式乘法。

10.1 FFT实现#

#include <bits/stdc++.h>
using namespace std;


const double PI = acos(-1);


struct Complex {
    double r, i;
    Complex(double r = 0, double i = 0) : r(r), i(i) {}
    Complex operator+(const Complex& c) const {
        return Complex(r + c.r, i + c.i);
    }
    Complex operator-(const Complex& c) const {
        return Complex(r - c.r, i - c.i);
    }
    Complex operator*(const Complex& c) const {
        return Complex(r * c.r - i * c.i, r * c.i + i * c.r);
    }
};


void fft(Complex a[], int n, int inv) {
    if (n == 1) return;


    Complex a0[n/2], a1[n/2];
    for (int i = 0; i < n/2; i++) {
        a0[i] = a[i * 2];
        a1[i] = a[i * 2 + 1];
    }


    fft(a0, n/2, inv);
    fft(a1, n/2, inv);


    Complex wn(cos(2 * PI / n), inv * sin(2 * PI / n));
    Complex w(1, 0);


    for (int i = 0; i < n/2; i++) {
        Complex t = w * a1[i];
        a[i] = a0[i] + t;
        a[i + n/2] = a0[i] - t;
        w = w * wn;
    }
}


vector<int> multiply(vector<int>& A, vector<int>& B) {
    int n = 1;
    while (n < A.size() + B.size()) n *= 2;


    Complex a[n], b[n];
    for (int i = 0; i < n; i++) {
        a[i] = i < A.size() ? Complex(A[i], 0) : Complex(0, 0);
        b[i] = i < B.size() ? Complex(B[i], 0) : Complex(0, 0);
    }


    fft(a, n, 1);
    fft(b, n, 1);


    for (int i = 0; i < n; i++) {
        a[i] = a[i] * b[i];
    }


    fft(a, n, -1);


    vector<int> result(n);
    for (int i = 0; i < n; i++) {
        result[i] = (int)(a[i].r / n + 0.5);
    }


    return result;
}

10.2 NTT实现#

const long long MOD = 998244353;
const long long G = 3;


long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}


void ntt(long long a[], int n, int inv) {
    if (n == 1) return;


    long long a0[n/2], a1[n/2];
    for (int i = 0; i < n/2; i++) {
        a0[i] = a[i * 2];
        a1[i] = a[i * 2 + 1];
    }


    ntt(a0, n/2, inv);
    ntt(a1, n/2, inv);


    long long wn = qpow(G, (MOD - 1) / n, MOD);
    if (inv == -1) wn = qpow(wn, MOD - 2, MOD);


    long long w = 1;
    for (int i = 0; i < n/2; i++) {
        long long t = w * a1[i] % MOD;
        a[i] = (a0[i] + t) % MOD;
        a[i + n/2] = (a0[i] - t + MOD) % MOD;
        w = w * wn % MOD;
    }
}

十一、分治优化DP#

11.1 决策单调性优化#

当DP转移满足决策单调性时，可以使用分治优化。

// dp[i] = min(dp[j] + cost(j+1, i)) for j < i
// 且决策点单调不减


long long dp[MAXN], cost[MAXN][MAXN];
int n;


void solve(int l, int r, int optL, int optR) {
    if (l > r) return;


    int mid = (l + r) / 2;
    int opt = -1;


    for (int k = optL; k <= min(mid - 1, optR); k++) {
        long long val = dp[k] + cost[k + 1][mid];
        if (opt == -1 || val < dp[mid]) {
            dp[mid] = val;
            opt = k;
        }
    }


    solve(l, mid - 1, optL, opt);
    solve(mid + 1, r, opt, optR);
}


int main() {
    // 初始化cost数组
    // ...


    dp[0] = 0;
    for (int i = 1; i <= n; i++) dp[i] = INF;


    solve(1, n, 0, n - 1);


    cout << dp[n] << endl;
    return 0;
}

时间复杂度：从O(n²)优化到O(n log n)

十二、经典分治题目#

12.1 最接近点对#

问题：平面上有n个点，求距离最近的两个点。

#include <bits/stdc++.h>
using namespace std;


struct Point {
    double x, y;
};


bool cmp_x(const Point& a, const Point& b) {
    return a.x < b.x;
}


bool cmp_y(const Point& a, const Point& b) {
    return a.y < b.y;
}


double dist(const Point& a, const Point& b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}


double closest_pair(vector<Point>& points, int l, int r) {
    if (r - l <= 3) {
        double minDist = 1e18;
        for (int i = l; i < r; i++) {
            for (int j = i + 1; j < r; j++) {
                minDist = min(minDist, dist(points[i], points[j]));
            }
        }
        sort(points.begin() + l, points.begin() + r, cmp_y);
        return minDist;
    }


    int mid = (l + r) / 2;
    double midX = points[mid].x;


    double d = min(closest_pair(points, l, mid),
                   closest_pair(points, mid, r));


    // 合并
    vector<Point> strip;
    for (int i = l; i < r; i++) {
        if (abs(points[i].x - midX) < d) {
            strip.push_back(points[i]);
        }
    }


    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size() &&
             strip[j].y - strip[i].y < d; j++) {
            d = min(d, dist(strip[i], strip[j]));
        }
    }


    return d;
}


int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }


    sort(points.begin(), points.end(), cmp_x);
    cout << fixed << setprecision(6) << closest_pair(points, 0, n) << endl;


    return 0;
}

12.2 天际线问题#

使用分治法求城市天际线轮廓。

vector<pair<int, int>> merge_skylines(vector<pair<int, int>>& left,
                                       vector<pair<int, int>>& right) {
    vector<pair<int, int>> result;
    int h1 = 0, h2 = 0;
    int i = 0, j = 0;


    while (i < left.size() && j < right.size()) {
        int x, h;
        if (left[i].first < right[j].first) {
            x = left[i].first;
            h1 = left[i].second;
            i++;
        } else if (left[i].first > right[j].first) {
            x = right[j].first;
            h2 = right[j].second;
            j++;
        } else {
            x = left[i].first;
            h1 = left[i].second;
            h2 = right[j].second;
            i++; j++;
        }


        h = max(h1, h2);
        if (result.empty() || result.back().second != h) {
            result.push_back({x, h});
        }
    }


    while (i < left.size()) result.push_back(left[i++]);
    while (j < right.size()) result.push_back(right[j++]);


    return result;
}

总结#

分治算法是算法设计中的基础思想，掌握分治需要：

  1. 理解分治思想：分解、求解、合并
  2. 掌握基础算法：归并排序、快速排序、二分查找
  3. 学会二分答案：最大化最小值、最小化最大值
  4. 深入高级技巧：CDQ分治、点分治、线段树分治
  5. 熟悉优化方法：FFT/NTT、分治优化DP

通过系统学习和大量练习，你将能够熟练运用分治算法解决各类竞赛问题。从CSP-S的基础二分到IOI的高级分治，分治思想将伴随你整个算法竞赛生涯。

推荐练习题目：

  • 洛谷P1226（快速幂）
  • 洛谷P1908（逆序对）
  • 洛谷P3810（三维偏序）
  • 洛谷P4178（点分治）
  • 洛谷P3803（FFT/NTT）
  • Codeforces 各种Div2 D/E题

坚持练习，你一定能精通分治算法！

分治算法详解：从CSP-S到IOI
https://myblog-590.pages.dev/posts/algorithm-divide-conquer/
作者
谢星宇
发布于
2026-01-21
许可协议
CC BY-NC-SA 4.0

相关文章

1

网络流与二分图匹配：从CSP-S到IOI

网络流算法完整教程，涵盖最大流、最小费用流、二分图匹配等核心内容

技术 2026年1月21日
2

博弈论算法详解：从CSP-S到IOI

博弈论完整教程，涵盖Nim游戏、SG函数、各类经典博弈问题

技术 2026年1月21日
3

数论算法详解：从CSP-S到IOI

数论算法完整教程，涵盖质数、GCD、快速幂、逆元、欧拉函数等核心内容

技术 2026年1月21日
图论算法详解
动态规划算法详解：从CSP-S到IOI
© 2026 谢星宇. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari