CDQ Divide And Conquer
(algo/offline/cdq_divide_and_conquer.hpp)

• View this file on GitHub
• Last update: 2026-07-07 22:10:04+09:00
• Include: #include "algo/offline/cdq_divide_and_conquer.hpp"

Overview

cdq_divide_and_conquer provides the standard recursive shape for offline CDQ algorithms. It solves the left half, solves the right half, and then calls a user callback for cross contributions from [left, middle) to [middle, right).

The public namespace is m1une::algo.

Functions

Function	Description	Complexity
cdq_divide_and_conquer(left, right, solve_cross)	Runs CDQ on [left, right).	$O(N)$ recursion overhead plus callbacks
cdq_divide_and_conquer(n, solve_cross)	Runs CDQ on [0, n).	$O(N)$ recursion overhead plus callbacks

The callback signature is solve_cross(int left, int middle, int right). Sorting, Fenwick updates, and rollback are intentionally left to the callback, because those details depend on the offline problem.

Example

#include "algo/offline/cdq_divide_and_conquer.hpp"

#include <vector>

int main() {
    std::vector<int> a = {3, 1, 2};
    long long inversions = 0;

    m1une::algo::cdq_divide_and_conquer(int(a.size()), [&](int l, int m, int r) {
        for (int i = l; i < m; ++i) {
            for (int j = m; j < r; ++j) {
                if (a[j] < a[i]) ++inversions;
            }
        }
    });
}

Required by

• Algorithms All (algo/all.hpp)
• Offline Algorithms All (algo/offline/all.hpp)

Verified with

• verify/algo/offline/cdq_divide_and_conquer.test.cpp

Code

#ifndef M1UNE_ALGO_OFFLINE_CDQ_DIVIDE_AND_CONQUER_HPP
#define M1UNE_ALGO_OFFLINE_CDQ_DIVIDE_AND_CONQUER_HPP 1

#include <cassert>

namespace m1une {
namespace algo {

template <class SolveCross>
void cdq_divide_and_conquer(int left, int right, SolveCross solve_cross) {
    assert(left <= right);

    auto dfs = [&](auto& self, int l, int r) -> void {
        if (r - l <= 1) return;
        const int middle = l + (r - l) / 2;
        self(self, l, middle);
        self(self, middle, r);
        solve_cross(l, middle, r);
    };
    dfs(dfs, left, right);
}

template <class SolveCross>
void cdq_divide_and_conquer(int n, SolveCross solve_cross) {
    assert(0 <= n);
    cdq_divide_and_conquer(0, n, solve_cross);
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_OFFLINE_CDQ_DIVIDE_AND_CONQUER_HPP

#line 1 "algo/offline/cdq_divide_and_conquer.hpp"



#include <cassert>

namespace m1une {
namespace algo {

template <class SolveCross>
void cdq_divide_and_conquer(int left, int right, SolveCross solve_cross) {
    assert(left <= right);

    auto dfs = [&](auto& self, int l, int r) -> void {
        if (r - l <= 1) return;
        const int middle = l + (r - l) / 2;
        self(self, l, middle);
        self(self, middle, r);
        solve_cross(l, middle, r);
    };
    dfs(dfs, left, right);
}

template <class SolveCross>
void cdq_divide_and_conquer(int n, SolveCross solve_cross) {
    assert(0 <= n);
    cdq_divide_and_conquer(0, n, solve_cross);
}

}  // namespace algo
}  // namespace m1une

Back to top page