前言
感觉这是个很厉害的算法呀,因为到处都在用,然而网上资料不是很多,到底是为什么呢?在终于参透了其中的奥妙之后我发现:它只是一个策略而已了。而且,不难。
原理简述
它用来干什么?
用于顶替一些复杂的数据结构,说白了呢,就是好写常数小。换一种理解方式呢,就是你不会也没什么关系。
当然有时候它的确是可以化简太多了,因为树套树什么的的确不好写哈,所以还是要学的。
还有个好处就是它占用的空间很少,也不需要离散什么的。
它的条件是什么?
- 可以离线
- 修改操作相对独立
题外话:二维偏序是个什么
二维偏序是CDQ分治的经典例题,所以说一下到底是个啥,其实就是那个二维树状数组的那种格式,在平面内,可以有两个元素无法比较大小,无法通过简单的排序得到答案。
举个例子就是平面上有很多点,求每个点左上方有多少个点,这就是二维偏序问题了。
正式介绍了
最常见的一个CDQ分治是归并排序求逆序对,没错,这就是CDQ分治,我们把它一般化就可以了(同时也可以看出它是可以被其他数据结构代替的,逆序对可以用树状数组求嘛)。
我们通过求逆序对来看看CDQ分治的过程。
递归处理左右两边之后,我们按照顺序处理左边元素对右边元素的影响。
完了。
当然这个影响的处理就是CDQ分治的核心了,中途有很多技巧嘛。
用的时候要注意对于排序那一维的选择,仔细想一想,其实很多时候是可以随便选的。。。只不过习惯上喜欢用时间或者下标来排序而已了。
还有就是输出答案的时候自己想点办法吧,这个应该没什么难的。
来看看CDQ更加本质的东西
最基础的CDQ分治处理的是二维的问题,其中把一维排序之后,就不用考虑这一维的影响了,然后处理另外一维,在加入了时间(一般体现为修改操作)这个元素后,由于把时间弄成了一维,那么它就只能处理一维的问题了。
通过这个原理回首一些数据结构,发现其中的确是有奥妙的,大多数数据结构都可以直接处理二维问题了。
如何向高维推广?
比如二维的话是(最简单情况):先排序一维,分治的时候排序第二维
三维就是:前两维同上,第三维就用树状数组来维护咯。
代码
没什么特别的哎,我把逆序对的贴上来吧(滑稽
这里是左闭右开
LL dvd(int *A,int x,int y)
{
if(y-x==)
return ;
int m=(x+y)/;
LL t3=,t1=dvd(A,x,m),t2=dvd(A,m,y);
int i=x,j=m,k=x;
while(i<m&&j<y)
{
if(A[i]>A[j])
{
t3+=m-i;
t[k++]=A[j++];
}
else
t[k++]=A[i++];
}
for(;i<m;)
t[k++]=A[i++];
for(;j<y;)
t[k++]=A[j++];
for(i=x;i<y;i++) A[i]=t[i];
return t1+t2+t3;
}