分治
289 字
1 分钟
分治
-
问题一分为二 —>递归(DFS)->合并答案
-
时间优化：O(nn)->O(n log n)
-
步骤
- 分：折半 min=(l+r)/2
- 治：左右递归 dfs(l,mid),dfs(mid+1,r)
- 合：跨中界的答案必须线性合并（否则白分）
- 返：max(左，右，跨中)或累加
模板
// 最大子段和——分治版（简洁注释）int dfs(int l,int r){ if(l==r) return a[l]; // 只剩一个元素，直接返回 int m=(l+r)>>1; // 折半 int ret=max(dfs(l,m),dfs(m+1,r)); // 左右子问题最优解
int sum=a[m], lmax=a[m]; // 向左延伸的最大后缀和 for(int i=m-1;i>=l;--i) lmax=max(lmax,sum+=a[i]);
sum=a[m+1]; int rmax=a[m+1]; // 向右延伸的最大前缀和 for(int i=m+2;i<=r;++i) rmax=max(rmax,sum+=a[i]);
return max(ret,lmax+rmax); // 跨中、左、右三者最值}// 逆序对——归并版（简洁注释）ll dfs(int l,int r){ if(l>=r) return 0; // 空或单元素，逆序对为 0 int m=(l+r)>>1; ll ret=dfs(l,m)+dfs(m+1,r); // 左右子区间逆序对累加
// 以下归并两个已排好序的子区间，并统计跨越中点的逆序对 int i=l,p1=l,p2=m+1; while(p1<=m&&p2<=r){ if(a[p1]<=a[p2]) b[i++]=a[p1++]; // 左侧小，无逆序对 else{ ret+=m-p1+1; // 左侧剩余全都 > a[p2] b[i++]=a[p2++]; } } while(p1<=m) b[i++]=a[p1++]; // 把剩余元素直接拷完 while(p2<=r) b[i++]=a[p2++]; for(int j=l;j<=r;++j) a[j]=b[j]; // 复制回原数组，供上层使用 return ret;}//时间复杂度O（n log n）文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
算法错题本
算法在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
2
数论
算法如果 $a$ 除以 $b$ 没有余数，那么 $a$ 就是 $b$ 的倍数，$b$ 就是 $a$ 的约数，记作 $b \mid a$。 约数，也称因数。
3
高精度
算法当数据的值特别大，超出各种基本数据类型的存储范围时，需要使用高精度算法来计算加减乘除。
4
贪心
算法思路 猜一个排序依据（比如按重量、按 deadline、按权值差等） 任取相邻两项 i, j 假设顺序错了，写出交换前/后只与这两头有关的代价/收益表达式 令“交换后更优”得不等式，化简成key(i) key(j)这个 key 就是 so…
5
二分
算法解集具“二段性”即可用：前一段不满足，后一段一定满足，或反之
随机文章随机推荐