分治基础

分治

分治算法是一种递归式的问题解决方法，其基本思路是将一个难以直接求解的大问题，拆分为若干个规模较小且结构相同或相似的子问题，分别求解后再合并得到原问题的解。这一思想体现了"化整为零、各个击破"的策略，是许多高效算法的基础。

分治算法的核心思想分为三步：

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

分治策略的关键要素：

问题可分解： 原问题能自然地划分为规模更小的子问题
子问题独立： 各子问题之间不存在相互依赖
合并可行： 能高效地将子问题的解合并为原问题的解
递归终止条件： 必须有递归出口，避免无限递归

我们已经学习过的二分查找算法本质也是一种分治策略，区别是二分查找是"分而弃之"，而分治算法更多的是"分而治之"。

经典分治问题：

区间极值问题

给定一个长度为 $n$ 的整数序列 $a_1,a_2,...,a_n$ ，以及 $q$ 次查询。每次查询给定区间 $[l,r]$ ，要求输出该区间的最大值。

对于这个问题，分治算法并非最优解——直接遍历区间元素的朴素算法，以及预处理后 $o(logn)$ 查询的线段树、 $o(1)$ 查询的稀疏表等结构，都能更好地解决此类问题。我们在此处引入区间极值问题，目的并非追求最优解，而是借助这一简单直观的问题，帮助大家熟悉分治算法的基本写作思路，为后续更复杂的应用打下基础。

令 $f(l,r)$ 表示区间 $[l,r]$ 的最大值。依据分治思想，我们取 $mid = (l+r)/2$ ，将区间 $[l,r]$ 从中点划分为 $[l,mid]$ 与 $[mid+1,r]$ 两个子区间，则有：

f(l,r) = \max(f(l,mid),\; f(mid+1,r))

递归地将每个区间继续划分，直到子区间仅包含一个元素为止——此时该区间的最大值即为该元素本身。随后自底向上逐层合并：分别得到左右子区间的最大值后，取二者中的较大者作为合并后区间的解。

这里加一个图：

核心代码如下：

int query(int l,int r){
    if(l==r)    return a[l]; //递归出口
    int mid=(l+r)/2;
    return max(query(l,mid),query(mid+1,r)); //将子问题的解合并
}

时间复杂度分析：

令 $T(n):$ 问题规模为 $n$ 时时间复杂度，将问题规模为 $n$ 划分为两个 $n/2$ 规模的子问题，则有：

T(n)=2T(n/2)+1

其中 $1$ 表示合并子问题解的时间开销。

再将 $n/2$ 的问题规模划分为两个 $n/4$ 的问题，则有：

T(n/2)=2*T(n/4)+1

将公式 $(3)$ 带入公式 $(2)$ 则有：

T(n)=4*T(n/4)+1+2

继续迭代下去则有：

$T(n)=n*T(1)+1+2+4+8+...+n/2$

因为 $T(1)=1$ ，使用等比数列求和公式可得： $T(n)=2*n-1$ 。因此该问题的时间复杂度为: $O(n)$ 。

递归层数与常数的对应关系如下：

层数	分解	常数项
1	$T(n) = 2T(n/2)$	$+1$
2	$= 4T(n/4)$	$+2$
3	$= 8T(n/8)$	$+4$
...
$\log_2 n$	$= nT(1)$	$+n/2$

最大子段和

给定一个长度为 $n$ 的序列 $a_i$ ( $1 \le i \le n$ )，请寻找一段连续的子段，使得子段中所有元素的和最大。

假定区间 $[l,r]$ ，区间中点 $mid=(l+r)/2$ , 令 $g(l,r)$ 为区间 $[l,r]$ 的最大子段和，分为三种情况：

$$g(l,r) = max \begin{cases} g(l,mid) &最大子段和位于左半区间\\ g(mid+1,r), & 最大子段和位于右半区间 \\ max\_suffix(l,mid)+max\_prefix(mid+1,r)& 最大子段和跨过左右两边 \end{cases}$$

其中， $max\_prefix(l,mid)$ 为区间最后前缀和(以右端点 $mid$ 开始的最大连续和)， $max_suffix(mid+1,r)$ 为区间最大前缀和(以左端点 $mid+1$ 为结尾的最大连续和)。

这里补一个图，形象说明上面的公式

基于上述分治思路，给出代码如下：

#include <bits/stdc++.h>

using namespace std;
const int N=2e5+5;
int a[N],n;

int max_SubArraySum(int l,int r){
    if(l==r)    return a[l];
    int mid=(l+r)/2;
    int mx1=max_SubArraySum(l,mid);//左半区间的最大子段和
    int mx2=max_SubArraySum(mid+1,r);//右半区间的最大子段和
    int lsum=INT_MIN,rsum=INT_MIN,sum=0;
    //求左区间的最大后缀和
    for(int i=mid;i>=l;i--){
        sum+=a[i];
        lsum=max(lsum,sum);
    }
    sum=0;
    //求右半区间的最大前缀和
    for(int i=mid+1;i<=r;i++){
        sum+=a[i];
        rsum=max(rsum,sum);
    }
    return max(max(mx1,mx2),lsum+rsum);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<maxSubArraySum(1,n)<<endl;
    return 0;
}

时间复杂度分析：

在合并阶段，求左半区间的最大后缀和以及右半区间的最大前缀和时，需要遍历当前区间内的所有元素，因此合并操作的时间复杂度为 $O(n)$ 。由于算法每次都将原问题划分为两个规模为 $n/2$ 的子问题，我们可以得出整个算法时间复杂度的递推关系式： $T(n)=2*T(n/2)+O(n)$ 。采用与区间极值问题相同的迭代方法可求得时间复杂度为: $O(nlogn)$ 。

与区间极值问题类似，分治法虽然能解决最大子段和问题，但并非该问题的最优解，因为利用贪心算法或动态规划可以将其进一步优化至 $O(n)$ 的线性时间。鉴于此，我们将在下一小节进一步探讨：究竟具备何种特征的问题，才最适合采用分治策略来解决。