浅谈一类分治算法

摘要

仍然是啃论文,这次啃一啃数据结构的部分

修改与询问

我们常常遇到数据结构题,要求我们维护修改与询问的操作。这些题目的要求各不相同,而操作之间的关系也各不相同。在满足特定关系的操作中,我们利用条件的线性性与相关性,可以将一类动态问题转化为静态问题。本文就是总结这样一类思想不难,实现不难的算法。

动态与静态

本人大概口糊一下吧,动态问题指的是修改与询问交叉出现的,而静态问题是指,一开始把所有修改都给出,然后再给出若干询问。

时间分治

对于满足 “修改独立,允许离线” 的数据结构题,我们可以采用对操作序列分治的方式,将动态的问题转化为静态的问题求解。

修改独立,是指修改操作对询问的贡献独立,修改操作之间互不影响效果。

具体的分治方法如下。我们对操作序列(按时间排序)分治:

  1. 后一半序列中的所有修改与前一半无关,也就是说前一半序列不受到后一半序列的影响,因此是一个规模更小的字问题,可以递归求解。
  2. 考虑后一半的序列中的询问。这个询问只和两部分的贡献有关:前一半序列中的所有修改操作做出的贡献、后一半序列中在该询问之前的修改操作做出的贡献。我们发现第一部分对后半部分的所有询问的贡献是一样的,也就是说这是一个静态问题,做出了前一半序列中的所有修改后,回答后一半序列中的若干询问。而对于第二部分的贡献,这部分贡献只存在于后一半序列中,与前一半无关,因此是一个递归子问题。由于我们的前提是修改操作互不影响,因此第一部分和第二部分的贡献可以合并。

对于算法复杂度而言,设求解动态问题的复杂度是 ,求解静态问题的复杂度是 .(包括合并的复杂度)

于是我们以一个 log 的代价,将动态的问题转化为静态的问题求解。

【例 1】共点圆

在平面直角坐标系中,Wayne 需要你完成 n 次操作,操作只有两种

  1. 0 x y,表示在坐标系中加入一个以 (x, y) 为圆心且过原点的圆。
  2. 1 x y,表示询问点 (x, y) 是否在所有已加入的圆的内部(含圆周),且至少在一个圆内部(含圆周)。

为了减少你的工作量,题目保证圆心严格在 x 轴上方(纵坐标为正),且横坐标非零。

,所有坐标绝对值不超过 10000。

我们考虑点 在圆 中的情况

相当于对于半平面 ,要求 在这个半平面内。因此问题转化为

  1. 添加一个点
  2. 给一个半平面,询问所有点是否在半平面内

做一下时间分治,问题转化为,给定一堆点,然后静态询问若干个半平面,问是否所有点都在半平面内。这个问题我们可以用凸包来做,显然只有凸包上的点最有可能跑到半平面外面,而这个点两边的斜率是 “夹住” 了半平面的斜率的,因此二分查找即可判定。复杂度 ,算上时间分治的复杂度,总复杂度 .

事实上,在分治的过程中,我们计算了前后两段的凸包后,可以直接线性合并凸包,类似归并排序。于是时间复杂度降为 .

二进制分组

对于满足 “修改独立,允许离线” 的数据结构题,我们可以时间分治;那如果强制在线呢?“修改独立,要求在线” 的题目,我们可以通过二进制分组的方式来求解。

对一个整数二进制分组,大概是这样的

这玩意儿怎么用在数据结构题上?我们把操作按二进制分组(比如前 1-16 个操作为一组,17-24 个操作为一组,以此类推),在每个组内统计总贡献。在线处理当前询问,我们查询之前建立的 个组的贡献即可。在线处理当前的修改操作,我们直接暴力重建末尾的分组,即可。比如对于前 27 个修改操作可以建出 16+8+2+1 的分组,那么对于第 28 个修改操作,我们把 2,1 的分组直接删掉,暴力重建一个 4 的分组,变成 16+8+4.

考虑一下复杂度,每次我们重建 个分组,其中 k 是当前操作数,假设统计贡献的复杂度是 ,总复杂度是

因此我们仍是以一个 的复杂度将动态问题转化为静态问题。并且这种算法常数较小,实现简单。

【例 2】在线共点圆

还是共点圆的问题,只不过要求在线。同样的,我们分出 个分组,每个组的点求凸包,对于半平面的询问就在 log 个组内查询,查询复杂度 . 总复杂度 .

时间倒流

时间倒流是一种处理删除操作的小技巧。时间分治的方法处理的问题是不带撤消操作的,一个操作对其后面的所有询问都产生贡献。而有些问题是带有删除操作的,这时我们首先正常地时间分治,然后面对的是带有若干删除操作的静态问题,再将序列倒过来,把删除变成插入,从而又变成一个不带删除的动态问题,再套一个时间分治求解。

不过需要注意的是,时间倒流是倒着统计操作的贡献,处理询问的,因此仍然只能用于允许离线的问题。

【例 3】动态共点圆问题

同样是共点圆问题的延伸

平面,n 次操作:

  1. 在坐标系中加入一个以 (x, y) 为圆心且过原点的圆。
  2. 删除一个之前插入的圆。
  3. 询问点 (x, y) 是否在所有已加入的圆的内部(含圆周),且至少在一个圆内部(含圆周)。

首先考虑时间分治,把操作序列分为前后两半。对于前半部分的操作是一个递归子问题,递归求解。对于在后半部分插入的圆,这些圆显然与前半部分无关,可以递归求解。而前半部分插入的圆在后半部分才删除,这些圆就对后半部分有影响。转化为半平面和凸包,因此我们的问题变成

  1. 询问一个半平面是否包含所有点
  2. 删除一个点

这个时侯,我们将操作序列翻转过来,删除变成插入,问题就变成了

  1. 询问一个半平面是否包含所有点
  2. 插入一个点

这个问题又可以用时间分治的方式求解,时间复杂度 ,使用归并优化过程可以做到 . 因此总复杂度 .

整体二分

整体二分是一种离线算法,它将询问分别处理到不同的答案区间中,然后递归处理各个区间的询问。具体地说,整体二分要求题目满足以下性质:

  1. 询问的答案具有单调性(可二分)
  2. 修改对答案的贡献独立,满足交换律结合律,具有可加性
  3. 允许离线

这时,我们二分答案,计算对应的贡献。如果累积的贡献不够,就说明当前二分的答案小于要求的答案;如果贡献超了,就说明当前二分答案大于了真实答案。这样就可以把相近的答案归到同一类处理。处理的实际过程是一个分治。整体二分算法较为灵活,因此我们结合例题加以阐释。这里给出一个整体二分的伪代码,方便理解。

Algorithm - Divide_And_Conquer(Q, L, R)
    //Q: 当前处理的询问序列
    //[L,R] 是当前答案区间

    if L = R then
        将 Q 中所有询问的答案设为 L
        return
    end if

    Mid := (L + R)/2
    Calculate(Q, L, Mid)
    //Calculate 用于计算 [L,Mid] 对 Q 中询问的贡献
    // 贡献存储早 Contribution 中,要求的答案是 want
    //current 是目前累积的贡献

    for i from 1 to Length(Q) do
        if Q[i].want <= Q[i].current + Contribution[i] then
            向数组 QL 末尾添加 Q[i]
        else 
            Q[i].current = Q[i].current + Contribution[i]
            向数组 QR 末尾添加 Q[i]
            // 贡献不够,说明真实答案大于 Mid
        end if
    end for

    // 分治处理
    Divide_And_Conquer(QL, L, Mid)
    Divide_And_Conquer(QR, Mid+1, R)

【例 4】动态区间第 K 小

一个长度为 n 初始值为 的序列,m 个操作:

  1. 单点修改序列的元素
  2. 区间查询第 k 小

区间第 k 小是一个可以二分计算的答案,那么考虑整体二分。假设当前二分的答案为 mid。二分将原问题转化为贡献计算,我们的任务变成

  1. 单点修改
  2. 区间查询比 mid 小的数的个数

我们发现,操作 2 的贡献是满足可加性的。因为比 mid 小的数等价于在区间 中的数,等价于在若干个不相交且并集为 的区间中的数的个数。如果贡献小于我们要求的 k,说明当前询问的答案是大于 mid,那么我们直接将 k 减掉贡献,下此不再统计 的元素。如果贡献大于 k,说明答案小于 mid,那么不能累加贡献,就在 的答案区间中继续二分即可。

那么,如何解决上述的任务呢?解决上述任务的复杂度不能关于 n 呈线性,因为我们的整体二分实际上会递归 次(完全二叉树的结点个数是 的),而不是二分答案的 次。我们的复杂度只能和当前处理序列的长度有关。于是我们可以利用树状数组,将处在当前答案区间中的数的贡献设为 1, 其他数的贡献是 0。对于修改操作,相当于我们把它拆成两个操作:在一个位置删除一个数、在一个位置插入一个数。这样就可以转化为贡献的修改,同样用树状数组维护。复杂度 . 其中 k 是当前操作序列的长度。那么结合主定理易知,总复杂度为 .

参考程序

#include<cstdio>
#include<algorithm>
#include<assert.h>
#include<cstring>
using namespace std;
const int N=1e6+5,M=1e6+5;
int n,m;
int a[N];

#define RED "\033[41m"
#define GRE "\033[42m"
#define NONE "\033[0m"

struct data{
    int type,i,j,k,id;
    // 对于 type==0-> 询问,那么 ijk 就是对应的意思
    // 对于 type==1-> 修改,那么 i 是下标位置,j 是键值,k 是修改值。
    /*void print(){if(type==0){printf(GRE"[QUERY]"NONE"[%d,%d] %d -th\n",i,j,k);
        }
        else {printf(RED"[MODIFY]"NONE"%d %d %d\n",i,j,k);
        }
    }*/
};
data d[M*2];
int ld;

namespace BIT{// 树状数组
    int c[N];
    void add(int pos,int val){for(int i=pos;i<=n;i+=i&-i)c[i]+=val;
    }
    int pre(int pos){
        int res=0;
        for(int i=pos;i>0;i-=i&-i)res+=c[i];
        return res;
    }
}

int ans[M];

data q1[N],q2[N];
void solve(int l,int r,int L,int R){// 对应的操作序列是 d[l..r],答案的二分区间是 [L,R]
    if(l>r)return;

    /*printf("solve(%d,%d,%d,%d)\n",l,r,L,R);
    for(int i=l;i<=r;i++)d[i].print();
    puts("");*/

    if(L==R){// 递归边界情况
        for(int i=l;i<=r;i++)if(d[i].type==0)ans[d[i].id]=L;
        return;
    }
    int mid=(L+R)>>1;
    int l1=0,l2=0;// 一定要放在里面定义!
    for(int i=l;i<=r;i++){// 将操作归类
        data now=d[i];
        if(now.type==0){int t=BIT::pre(now.j)-BIT::pre(now.i-1);
            if(now.k<=t)q1[++l1]=now;
            else now.k-=t, q2[++l2]=now;
        }
        else {if(L<=now.j&&now.j<=mid) BIT::add(now.i,now.k), q1[++l1]=now;
            else q2[++l2]=now;
        }
    }
    //assert(l1+l2==r-l+1);
    for(int i=1;i<=l1;i++)// 还原修改
        if(q1[i].type==1)BIT::add(q1[i].i,-q1[i].k);

    //for(int i=1;i<=n;i++)assert(BIT::c[i]==0);// 调试

    for(int i=1;i<=l1;i++)d[l+i-1]=q1[i];
    for(int i=1;i<=l2;i++)d[l+l1+i-1]=q2[i];

    /*printf("分完后 \n");
    for(int i=l;i<=r;i++)d[i].print();
    puts("");*/

    solve(l,l+l1-1,L,mid);
    solve(l+l1,r,mid+1,R);
}

int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){// 把初始化转化为添加操作
        scanf("%d",&a[i]);
        d[++ld]=(data){1,i,a[i],1};
    }
    for(int ii=1;ii<=m;ii++){char op[3];
        int i,j,k,t;
        scanf("%s",op);
        if(op[0]=='Q'){// 询问
            scanf("%d%d%d",&i,&j,&k);
            d[++ld]=(data){0,i,j,k,ii};
        }
        else {// 修改
            scanf("%d%d",&i,&t);
            d[++ld]=(data){1,i,a[i],-1}, d[++ld]=(data){1,i,t,1};
            a[i]=t;// 第二发的时侯忘写这行了
        }
    }
    memset(ans,-1,sizeof(ans));
    solve(1,ld,1,1e9);// 交的时侯忘把 10 改成 1e9 了
    for(int i=1;i<=m;i++)
        if(~ans[i])printf("%d\n",ans[i]);
    return 0;
}
/*
 * 又来写整体二分了。。。
 * 二分答案,然后针对二分的区间,将操作分为两部分
 * 对于当前答案区间 [L,R],二分的值为 mid,那么我们知道这时序列中的操作
 * 的已经累加了 [1,L) 的贡献。而我们先处理 [L,mid],再处理 [mid+1,r]
 */

CDQ 分治

CDQ 即陈丹琦。CDQ 分治基于一个重要的思想:

  1. 分治
  2. 处理一个子问题对另一个子问题的贡献

它与整体二分是同源的。先从一个经典问题引入:三维偏序。

【例 5】三维偏序

给 n 个三维点 (x,y,z),对每个点 i 求满足 的点 j 的个数

先考虑二维偏序,这个问题,我们将二维点按 x 升序排序,那么显然对点 i 需要考虑 的点的个数,即 的贡献。那么维护一个树状数组即可。

考虑三维偏序。先将点按 x 升序排序。那么问题需要统计 的点的个数。如果没有 这个条件,这就是一个经典的二维偏序。于是我们利用分治的思想,把点序列分为前后两半,可以递归处理两个子问题。

那么我们需要处理左边对右边的贡献,于是发现这个问题是已经满足了 的条件,于是就是一个经典的二维偏序问题。二维偏序需要对点排序,也就是说我们要对左边的点按 y 升序排序。这个可以在回溯的时侯做归并排序实现。于是总体的算法是,先归并,再把原来属于左边的点加入树状数组,对原来属于右边的点统计贡献即可。复杂度 .

参考文献

许昊然,《浅谈数据结构题的几个非经典解法》,2013 信息学奥林匹克中国国家队候选队员论文


  转载请注明: Sshwy's Blog 浅谈一类分治算法

 上一篇
二维凸包 二维凸包
摘要 二维凸包是计算几何中比较入门的部分 二维凸包的定义对于平面上的若干个点 ,二维凸包指的是一个面积最小的凸多边形,把所有的点包含在内部。这个凸多边形以点集的形式表示。实际上可以理解为用一个橡皮筋包含住所有给定点的
2019.05.06
下一篇 
主定理 主定理
摘要 花个 10 分钟学一学主定理 形式假设有递归关系式 T(n)=aT\left(\frac{n}{b}\right)+f(n)其中 . 为问题规模,而 a 为递归子问题的数量,$\frac{n}
2019.05.05
  目录