高效算法中的二分答案与分治结构设计

核心逻辑与数学原理

二分答案（Binary Search on Answer）

单调性是二分答案的数学基石。设解空间为 $D$，判定函数为 $f: D \to \{0, 1\}$。若 $f(x)$ 满足单调递增或递减性质，即：

$$\forall x_1, x_2 \in D, x_1 < x_2 \implies f(x_1) \le f(x_2)$$

则可通过对解空间 $D$ 进行二进制折半划分，在 $O(\log |D|)$ 次判定内逼近最优解 $x^*$。每次决策剔除一半不合法值域，将最优化问题退化为判定性问题。

分治二叉树结构（Divide and Conquer Tree）

将序列 $A[1..N]$ 的空间区间转化为时间上的树形分治过程。对于区间 $[l, r]$，取 $mid = \lfloor \frac{l+r}{2} \rfloor$，递归构造左子树 $[l, mid]$ 与右子树 $[mid+1, r]$。整个分治轨迹在逻辑上抽象为一棵高度为 $O(\log N)$ 的完全二叉树。通过对这棵逻辑二叉树的自底向上合并（如线段树的 PushUp 逻辑）或自顶向下传导（如 CDQ 分治的左侧贡献右侧），将 $O(N^2)$ 的全局序列问题拆解为 $\log N$ 层局部区间的叠加。树的每一层总工作量控制在 $O(N)$，总体时间复杂度收敛于 $O(N \log N)$。

算法推导与分治结构设计

二分答案的边界推导

对于满足“全 $1$ 后全 $0$”单调性的判定函数，求解最后一个使 $f(x)=1$ 成立的极大值 $x^*$：初始化双指针 $l = \min(D), r = \max(D)$。

令 $mid = l + \lfloor \frac{r-l+1}{2} \rfloor$，防止 $l+r$ 导致的整型溢出，且上取整避免 $r = l+1$ 时死循环。
若 $f(mid) == 1$，说明答案在 $[mid, r]$ 闭区间内，更新 $l = mid$。
若 $f(mid) == 0$，说明答案在 $[l, mid-1]$ 闭区间内，更新 $r = mid - 1$。
当 $l == r$ 时终止， $l$ 即为所求。

分治二叉树的区间分解

在序列分治中，任意询问区间 $[L, R]$ 在分治二叉树上会被精确切割为 $O(\log N)$ 个非叶节点。设当前分治节点为 $u$，管辖序列区间 $[l, r]$。

若 $[L, R] \supseteq [l, r]$，直接提取该节点预处理的区间特征，终止递归。
若 $L \le mid$，递归进入左子树 $(u \ll 1)$。
若 $R > mid$，递归进入右子树 $(u \ll 1 | 1)$。跨越 $mid$ 的跨区间统计，其数学本质是左子树的后缀信息与右子树的前缀信息进行代数卷积。

C++ 标准源码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 模拟 NOIP 经典题型：最大化最小值问题（如木棒切割、跳石头）
// 判定函数：检查在每段长度至少为 check_val 的限制下，序列能否被切分为至少 k 段
bool check_feasibility(const vector<int>& stone_pos, int target_segments, int max_dist, int check_val) {
    int count = 0;
    int last_pos = 0;

    for (size_t i = 0; i < stone_pos.size(); ++i) {
        if (stone_pos[i] - last_pos >= check_val) {
            count++;
            last_pos = stone_pos[i];
        }
    }
    // 致命踩坑点：判定边界需严格包含到达终点的最后一段距离，否则少算一段导致逻辑错误
    if (max_dist - last_pos < check_val) {
        count--;
    }

    return count >= target_segments;
}

// 分治二叉树结构：区间最大连续子段和（线段树核心逻辑模拟）
struct SegmentNode {
    long long sum;
    long long lmax;
    long long rmax;
    long long tmax;
};

// 自底向上合并逻辑
SegmentNode merge_nodes(const SegmentNode& left, const SegmentNode& right) {
    SegmentNode res;
    res.sum = left.sum + right.sum;
    res.lmax = max(left.lmax, left.sum + right.lmax);
    res.rmax = max(right.rmax, right.sum + left.rmax);
    // 跨越 mid 的核心逻辑：左子树右最大 + 右子树左最大
    res.tmax = max({left.tmax, right.tmax, left.rmax + right.lmax});
    return res;
}

// 分治二叉树建树过程
void build_divide_tree(vector<SegmentNode>& tree, const vector<int>& a, int u, int l, int r) {
    if (l == r) {
        tree[u] = {a[l], a[l], a[l], a[l]};
        return;
    }
    int mid = l + ((r - l) >> 1); // 致命踩坑点：位运算优先级低，必须加外层括号
    build_divide_tree(tree, a, u << 1, l, mid);
    build_divide_tree(tree, a, u << 1 | 1, mid + 1, r);
    tree[u] = merge_nodes(tree[u << 1], tree[u << 1 | 1]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 1. 二分答案模块测试
    int L = 25, n = 5, m = 2; // 总长25，5块石头，移走2块（即分成4段）
    vector<int> stones = {2, 11, 14, 17, 21};

    int l_ans = 1, r_ans = L, ans = 0;
    while (l_ans <= r_ans) {
        int mid_ans = l_ans + ((r_ans - l_ans) >> 1);
        if (check_feasibility(stones, n - m, L, mid_ans)) {
            ans = mid_ans;
            l_ans = mid_ans + 1; // 寻找极大值，向右逼近
        } else {
            r_ans = mid_ans - 1;
        }
    }

    // 2. 分治树模块测试
    int seq_len = 4;
    vector<int> seq = {0, -1, 2, 3}; // 1-indexed 模拟
    vector<SegmentNode> divide_tree(seq_len * 4);
    build_divide_tree(divide_tree, seq, 1, 1, seq_len - 1);

    return 0;
}

NOIP 实战避坑指南

位运算优先级导致的死循环与错误划分 为了追求常数优化，选手常将 mid = (l + r) / 2 写成 mid = l + r >> 1 或 mid = l + (r - l) >> 1。由于加减法运算符 + - 的优先级高于移位运算符 >>，表达式会被解释为 mid = (l + (r - l)) >> 1 甚至 mid = (l + r) >> 1。在 $l$ 和 $r$ 较大时直接导致整型溢出，或在二分边界收缩时因计算错误陷入死循环。必须强制添加括号：mid = l + ((r - l) >> 1)。
二分死循环与值域无穷化漏洞 在编写“最大化最小值”与“最小化最大值”两类不同的二分时，更新指针常犯混淆错误。若 mid 采用向左取整 l + ((r - l) >> 1)，当 l = r - 1 时，mid 始终等于 l。此时如果分支逻辑内出现 l = mid，则区间不再缩小，直接挂锁死循环。必须根据 l = mid 还是 r = mid 严格对应修改 mid 的取整方向。

经典 NOIP/洛谷真题

洛谷 P2678 [NOIP2015 提高组] 跳石头

题意描述：给定一根轴上的起点、终点和 $N$ 个石头的位置，要求移走至多 $M$ 个石头，使得剩下的石头之间最短距离的最大。
问题本质与核心思路：最经典的“最大化最小值”问题。直接搜索复杂度呈指数级。问题具备显然的单调性：若最短距离为 $x$ 满足条件，则小于 $x$ 的所有距离必然也能通过移走更少的石头来满足。因此本质是二分答案。判定函数 $f(x)$ 采用贪心策略：从左往右扫描，若相邻两石头距离小于 $x$，则必须移走后一块石头，最后统计总移走数量是否 $\le M$。

洛谷 P4145 上帝造题的七分钟 2 / 花神游历各国

题意描述：给定一个序列，支持两种操作：区间所有数开平方取整，询问区间和。序列元素 $\le 10^{12}$。
问题本质与核心思路：分治二叉树结构的高级应用。一个 $10^{12}$ 级别的数在经过至多 6 次开方后就会变成 $1$。利用分治二叉树（线段树）结构管辖区间，每个节点维护该区间最大值。在递归分治修改时，若发现当前节点的区间最大值 $\le 1$，说明该子树内所有元素均已降为 $1$（开方后保持不变），直接触发剪枝回归。利用树形结构对无效分治直接切断，将势能分析引入分治结构，使总时杂度稳定在 $O(N \log N)$。