块状链表(1) ■向量 定位0(1),增奶0(m) 链表 定位0(m),增奶0(1) 块状链表 定位0(m12),增奶0(m12)
块状链表（1） ▪ 向量 • 定位O(1)，增删O(n) ▪ 链表 • 定位O(n)，增删O(1) ▪ 块状链表 • 定位O(n1/2)，增删O(n1/2)
块状链表(2) 8 006-[4_□→[0 Ato Inserto Erase( Update Maxo Min(- RMQ 常被用在别的复杂算法中来降低复杂度 如CA的0(m)-0(1)算法
块状链表（2） ▪ 常被用在别的复杂算法中来降低复杂度 • 如LCA的O(n) – O(1)算法 0 0 60 4 0 61 3 1 2 At() Insert() Erase() Update() Max() Min() - RMQ
后继数组(1) ■问题:给一个纸条涂色,每次用某种颜色 涂某个连续区间,问最后纸条上的颜色情 况。(纸条长度L,涂色次数N) 朴素算法:O(L×N) 线段树:O(ogL×N) 后继数组:O(L+N)
后继数组（1） ▪ 问题：给一个纸条涂色，每次用某种颜色 涂某个连续区间，问最后纸条上的颜色情 况。（纸条长度L，涂色次数N） ▪ 朴素算法：O( L×N ) ▪ 线段树：O( logL×N ) ▪ 后继数组：O( L＋N )
后继数组(2) 反向处理 加开一个一维数组,记录下一个未涂色点的位置 (NO冬令营2005朱泽园) 012845678901213 12|311999911118 7,11绿色
后继数组（2） ▪ 反向处理 ▪ 加开一个一维数组，记录下一个未涂色点的位置 ▪ （NOI冬令营2005 朱泽园） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 × [5,8] 蓝色 9 9 9 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 [3,10] 红色 11 11 11 11 [7,11] 绿色 12