ACM之数据结构.pptVIP

数据结构 湖南师范大学 罗迅 问题 RMQ：Range Minimum Maximum Query 在一个序列上，给定区间，求区间极值 LCA：Lowest Common Ancestor 最近公共祖先是一个节点，是指定两点的祖先，且深度尽量深 RMQ 给定一个序列A，问A[i,j]的极值，一般会问极值所在的下标，而不是问极值本身 如果只问一次，O(n) 现在的问题是，不停的查询同一个序列的不同区间内的极值 暴力法 矩阵M[n][n]，令M[i][j]是A[i,j]的极值 做一个双重循环即可，O(n2) 以后每次查询，只需O(1) 空间也是O(n2) Sparse Table算法 矩阵M[n][logn+1] M[i][j]是区间A[i,i+2j)的极值 矩阵M的元素值的确定：类似于倍增算法 源代码 RMQ解法 已知M[n][logn]，问A[i,j]的极值 令k=log(i-j+1) ST算法 预处理：O(n*logn) 查询：O(1) 空间复杂度： O(n*logn) /tc?module=Staticd1=tutorialsd2=lowestCommonAncestor 题目列表 POJ3264，标准RMQ POJ3368，RMQ的一个扩展应用 线段树算法 预处理：O(n) 查询：O(logn) 空间复杂度： O(n) 线段树这种数据结构可以解决多种区间问题，不局限于RMQ 线段树图例 线段树是二叉树 每一个节点表示一个区间的值 例，右图5个节点分别保存了区间极值 根节点保存了全区间极值 叶子节点保存了单格值本身 静态数组实现线段树 线段树本质上是二叉树，静态数组实现线段树，实际上就是数组实现二叉树 如果问题规模是n，用于保存二叉树的 静态数组不会超过4n 令数组为St[] 以1为根节点 lson(x) ( (x) 1 ) rson(x) ( (x) 1 | 1 ) 线段树操作 build(idx,left,right) if left == right 确定单元格数值St[idx] mid = (left+right)1 build(lson(idx),left,mid) build(rson(idx),mid+1,right) query(idx,left,right,a,b) if a=left right=b return St[idx] mid = (left+right)1 if a = mid ans1 = query(lson(idx),left,mid,a,b) if b mid ans2 = query(rson(idx),mid+1,right,a,b) return MAX(ans1,ans2) 线段树适用问题 线段树可以查询极值，也可以查询区间和 线段树可以用于动态更新、查询 典型问题： 一个序列的整数 有更新操作，更新分为单点更新和成段更新 有查询操作，要求回答区间值 线段树操作 update(idx,left,right,sn,num) if left == right St[idx] += num int mid = (left+right) 1 if sn = mid update(lson(idx),left,mid,sn,num) else update(rson(idx),mid+1,right,sn,num) calDad(idx) calDad(idx) St[idx] = MAX(St[lson(idx)],St[rson(idx)]) 线段树延迟操作 对于区间成段更新，延迟操作是必须的 对于每一个成段更新，只更新到完整的段就可以了，而不必更新更深层次的节点 只有查询或者再次更新更深节点的时候才更新 延迟操作示例 成段更新1:3 此时只要更新根节点即可 如果接下来需要查询1:3，那么直接得结果 如果查询1:2，那么需要先更新1:2，再查询 延迟操作实现 实现延迟操作需要增加一个域，用来保存更新信息，用于其子节点 还需要一个函数，利用父节点更新信息去计算子节点更新后的结果 更多内容 /index.php/segment-tree-complete/ 题目列表 hdu1166，区间和 hdu1754，区间极值 hdu1394 hdu2795 hdu1698，成段更新 hdu3468，成段更新 并查集 处理不相交集合的合并和查询 Union find set 一般采用树状的逻辑结构 物理结构使用数组即可 father[3] = 2 father[2] = 2 并查集的查询 查询：求指定节点的始祖 优化：顺便将所经过的节点都指向始祖 k = father[x]; return k == x