分治:为运算表达式设计优先级

241. 为运算表达式设计优先级

 

最长数对链

646. 最长数对链

 

字符串

151. 翻转字符串里的单词

179. 最大数

Collections.sort和Arrays.sort自定义排序/部分排序

归并

315. 计算右侧小于当前元素的个数

327. 区间和的个数

线段树

数组下标[i, j]–>线段树[i, (i+j)/2]和[(i+j)/2+1, j]

线段树数组空间为4*len(arr)=4n,证明如下:
预备:二叉树用满二叉树存储
情况一:所有的元素都在最后一层,则分支节点个数为n-1,共需要2n-1空间,已经为满二叉树,不需要补空间;
情况二:只有2个节点在最有一层,另外n-2个节点在倒数第二层,则需要对这n-2个节点补充左右孩子,则需要2(n-2)=2n-4,原始二叉树共有2n-1个节点,那么一共有2n-1+2n-4=4n-5<4n;
综上:开4n空间

307. 区域和检索 – 数组可修改

线段树详解

【数据结构】线段树(Segment Tree)

线段树开4N空间证明

processon