分治
​	分治分治，分而治之。 所以分治这个算法的过程就是：分解 -> 解决 -> 合并。
分治和递归的关系很大：
递归是一种编程技巧，一种解决问题的思维方式；分治算法很大程度上是基于递归的，解决更具体问题的算法思想。
分治法能解决的问题一般有如下特征：

该问题的规模缩小到一定的程度就可以容易地解决。
该问题可以分解为若干个规模较小的相同问题。
该问题所分解出的各个子问题是相互独立的，即子问题之间没有关联。

这里我们拿归并排序举个例子：
归并排序
归并排序的基本流程如下。
void merge_sort(一个数组){
    if (很容易处理) return;
    merge_sort(左半个数组);
    merge_sort(右半个数组);
    merge(左半个数组，右半个数组);
}

具体的代码如下
public static void merge_sort(int[] a, int l, int r){
    if (l >= r) return; // 如果只有一个元素， 就不用排序了， 直接返回。
    int mid = (l + r) >> 1;
    merge_sort(a, l, mid);  // 递归处理左区间的数组
    merge_sort(a, mid+1, r);  // 递归处理右区间的数组

    int i = l, j = mid+1,pos = l;   // 合并两个有序的数组。 这里的 b 是一个静态数组， 开在函数的外面。
    while(i <= mid && j <= r){   // 比较左右区间的数组， 每次找一个最小的放到 b 数组中。 直到左右区间的数组有一个没有数字了。
        if (a[i] < a[j]) {
            b[pos] = a[i]; i++;
        } else {
            b[pos] = a[j]; j++;
        }
        pos++;
    }
    // 下面的两个 while 语句，只会有一个会执行。
    while(i <= mid) b[pos++] = a[i++];  // 如果 左区间数组还有数， 放到 b 数组里面。
    while(j <= r) b[pos++] = a[j++];   // 如果 右区间数组还有数， 放到b 数组里面。
    for (i = l; i <= r; ++i)   // 此时 b 数组已经有序了， 然后把数放回 a 数组。
        a[i] = b[i];
}

思路分析


代码实现
package com.atguigu.dac;

public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(5,'A','B','C');

    }

    //汉诺塔移动的方法
    //使用分治算法
    public static void hanoiTower(int num,char a,char b,char c){
        //如果只有一个盘
        if(num==1){
            System.out.println("第1个盘从"+a+"->"+c);
        }else {
            //如果我们n>=2情况，我们总是可以看做是两个盘1.最下边的一个盘2.上面的所有盘
            //1./先把最上面的的所有盘A->B,移动过程会使用到C
            hanoiTower(num-1,a,c,b);
            //2.把最下边的盘A->C
            System.out.println("第"+num+"个盘从"+a+"->"+c);
            //3.把B塔的所有盘从B->C,移动过程会使用到A
            hanoiTower(num-1,b,a,c);
        }
    }
}

分治算法的核心思想
  分治算法的核心思想就是四个字,分而治之,也就是将原来的问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解.

  看起来有点像递归,不过要知道分治算法是一种处理问题的思想,递归是一种编程技巧.看起来像是因为分治算法一般都比较适合用递归去实现
分治算法递归实现步骤
①	分解：将原问题分解问一系列的子问题；

②	解决：递归地求解各个子问题，若子问题足够小，则直接求解。

③	合并：将子问题的结果合并为原问题。
分治算法的适用条件
①	原问题与分解的小问题之间具有相同的模式

②	原问题分解成子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。

③	具有分解终止条件，即当问题足够小可以直接求解

④	可以将子问题合并成原问题，而这个合并操作复杂度不能太高，否则起不到减小算法整体复杂度的效果。
应用-如何变成求出一组数据的有序对个数或者逆序对个数？
  其实这个问题就是求一组数据的逆序对个数，比如我们有n个数据，我们期望从小到大排列，那么完全有序的数据的有序度是n(n-1)/2，逆序度是0；相反，倒序排列的数据的有序度为0，逆序度是n(n-1)/2.所以一般就是通过计算有序对或者逆序对个数来表示数据的有序度或者逆序度的。那么如何求逆序对个数呢

  最简单的办法就是拿每个数字跟后边的数字比较，看看有几个比自己小。这样把每个数字都考察一遍之后，将比自己小的数字个数加起来求和就得到逆序对个数了，这种办法效率比较低，时间复杂度O(n^2).

  更高效的办法就是使用分治算法，分治算法就是把数组A分为A1和A2凉拌，分别计算A1和A2的你虚度个数K1和K2，然后再计算A1和A2之间的逆序对个数K3，这样以来数组A的逆序度就是K1+K2+K3.那么如何计算A1和A2之间的逆序度？你能否想到归并排序呢？

  归并排序算法那中有一个关键操作就是将两个有序小数组，合并成一个有序的大数组。其实这个合并的过程中，我们就刻印计算这两个小数组的逆序对个数。每次合并我们都计算逆序对个数，把这些计算出来的逆序对个数求和，就是这个数组的逆序对个数了。

如图：


private int num = 0; // 全局变量或者成员变量

public int count(int[] a, int n) {
  num = 0;
  mergeSortCounting(a, 0, n-1);
  return num;
}

private void mergeSortCounting(int[] a, int p, int r) {
  if (p >= r) return;
  int q = (p+r)/2;
  mergeSortCounting(a, p, q);
  mergeSortCounting(a, q+1, r);
  merge(a, p, q, r);
}

private void merge(int[] a, int p, int q, int r) {
  int i = p, j = q+1, k = 0;
  int[] tmp = new int[r-p+1];
  while (i<=q && j<=r) {
    if (a[i] <= a[j]) {
      tmp[k++] = a[i++];
    } else {
      num += (q-i+1); // 统计 p-q 之间，比 a[j] 大的元素个数
      tmp[k++] = a[j++];
    }
  }
  while (i <= q) { // 处理剩下的
    tmp[k++] = a[i++];
  }
  while (j <= r) { // 处理剩下的
    tmp[k++] = a[j++];
  }
  for (i = 0; i <= r-p; ++i) { // 从 tmp 拷贝回 a
    a[p+i] = tmp[i];
  }
}

sszx dzy 20%
分治
分而治之
归并排序
分治思想的最简单体现，将具有特征的问题分解成子问题，子问题可用同样方法（即递归）处理。对于子问题之间的联系，特殊处理。
求逆序对
与归并排序密不可分，例：
1 2 3 4   1 2 3 4
1 2 3 4   5 6 7 8

主定理
求递归式的时间复杂度
平面上的分治
在平面上按x坐标排序分治，再在归并排序过程中考虑y坐标。
练习题
CF480E
树分治
求树上距离不大于k的点对个数，即路径。树分治就是解决树上路径问题的高效算法。
分为点分治和边分治
练习题
SPOJ FTOUR2（求选择不超过k个黑点的路径最大权值）：点分治
BZOJ2152（求2个点之间路径权值和是3的倍数的概率）：
BZOJ1758（）：分数规划+长链剖分
CDQ分治
CDQ分治需要题目支持离线算法，且修改操作互不影响
例题：陌上花开（BZOJ3262）
Des：求比每个元素的三种属性都小的元素个数

Sol：CDQ分治
练习题
BZOJ1176（维护矩阵，支持单点修改和范围查询）：
BZOJ3295,CQOI2011（动态逆序对:CDQ分治经典例题，删除元素的同时求逆序对个数）：
BZOJ2716/2648（SJY摆棋子：在棋盘上放下黑棋和白棋，对于白棋输出这个白棋和离它最近的黑棋之间的距离，此处的近和距离指曼哈顿距离）：二维偏序||kdtree
总结
题单:https://www.luogu.com.cn/training/57283