数据结构并查集教学资料ppt电子教案课件.ppt

并查集 回顾 并查集 union findset 是一种用于分离集合操作的抽象数据类型 它所处理的是 集合 之间的关系设想需要对不相交集合 disjoinset 进行两种操作 1 检查某元素属于哪个集合 2 合并两个集合 执行n次合并和m m n 次查询 并查集可以实现o 1 的平摊复杂度 并查集的实现 1 用一棵树来代表一个集合 集合里的每个元素都是树的一个节点 2 用树根来唯一标示这棵树 这个集合 3 那个元素作为根无所谓 只要属于同一集合的根相同4 所有的这些集合构成了一个森林 路径压缩 找到根节点之后 将路径上的节点都直接链接到根节点 这样在下次查找时 便可以减少查找次数 这一优化称为路径压缩 并查集的拓展 记录更多的信息比如 两个结点的相对关系信息的表示 表示并查集的森林的边带上权 偏移量 食物链 动物王国中有三类动物a b c 这三类动物的食物链构成了有趣的环形 a吃b b吃c c吃a 现有n个动物 以1 n编号 每个动物都是a b c中的一种 但是我们并不知道它到底是哪一种 有人用两种说法对这n个动物所构成的食物链关系进行描述 第一种说法是 1xy 表示x和y是同类 第二种说法是 2xy 表示x吃y 此人对n个动物 用上述两种说法 一句接一句地说出k句话 这k句话有的是真的 有的是假的 当一句话满足下列三条之一时 这句话就是假话 否则就是真话 1 当前的话与前面的某些真的话冲突 就是假话 2 当前的话中x或y比n大 就是假话 3 当前的话表示x吃x 就是假话 你的任务是根据给定的n 1 n 50 000 和k句话 0 k 100 000 输出假话的总数 合并同类 查找两种动物是否属于同一个集合 表示它们是同类 那x吃y怎么表示 3类动物3个集合 怎么确定xy是哪一类 我们用偏移量offset a b 表示a和b的关系 offset a b 0表示a和b是同类 offset a b 1表示a吃b offset a b 2表示b吃a 那么对任意种类东西c 显然offset a b offset a c offset c b 3这个关系式表明 a和b的关系可以通过a和根的关系以及b和根的关系推断出来 由上述结论得 同一集合内任意元素关系可推出 即关系已知 将确定关系的两个动物 合并为一个集合若两个动物不在同一个集合 那么关系未知 偏移量的更新 路径压缩 offset a 表示a与其父节点的关系设原fa a p 路径压缩使fa a rootoffset a root offset a p offset p root 3即offset a offset a offset p 3 线段树 部分引用pku 郭炜的ppt 线段树 树 是一棵树 而且是一棵二叉树 线段 树上的每个节点对应于一个区间 同一层的节点所代表的区间 相互不会重叠 同一层节点所代表的区间 加起来是个连续的区间 叶子节点的区间是单位长度 不能再分了 线段树是一棵二叉树 树中的每一个结点表示了一个区间 a b a b通常是整数 每一个叶子节点表示了一个单位区间 对于每一个非叶结点所表示的结点 a b 其左儿子表示的区间为 a a b 2 右儿子表示的区间为 a b 2 1 b 除法去尾取整 区间 1 9 的线段树 线段树的平分构造 实际上是用了二分的方法 若根节点对应的区间是 a b 那么它的深度为log2 b a 1 1 向上取整 叶子节点的数目和根节点表示区间的长度相同 区间分解 分解的规则就是 如果有某个节点代表的区间 完全属于待分解区间 则该节点为 终止 节点 不再继续往下分解所有 终止 节点所代表的区间都不重叠 且加在一起就恰好等于整个待分解区间 区间 1 9 的线段树上 区间 2 8 的分解 区间分解的时候 每层最多2个 终止节点 所以终止节点总数也是log n 量级的 x代表终止节点 上述情况不可能发生 线段树的特征 1 线段树的深度不超过log2 n 1 向上取整 n是根节点对应区间的长度 2 线段树上 任意一个区间被分解后得到的 终止节点 数目都是log n 量级 线段树上更新叶子节点和进行区间分解时间复杂度都是o log n 的这些结论为线段树能在o log n 的时间内完成一个区间的建树 插入数据 更新数据 查找 统计等工作 提供了理论依据 敌兵布阵 一个正整数n n 50000 表示敌人有n个工兵营地 接下来有n个正整数 第i个正整数ai代表第i个工兵营地里开始时有ai个人 1 ai 50 接下来每行有一条命令 命令有4种形式 1 addij i和j为正整数 表示第i个营地增加j个人 j不超过30 2 subij i和j为正整数 表示第i个营地减少j个人 j不超过30 3 queryij i和j为正整数 i j 表示询问第i到第j个营地的总人数 每组数据最多有40000条命令 建立 点更新 区间更新 查询 线段树适用于多次查询用线段树解题 关键是要想清楚每个节点要存哪些信息 当然区间起终点 以及左右子节点指针是必须的 以及这些信息如何高效更新 维护 查询 不要一更新就更新到叶子节点 那样更新效率最坏就可能变成o n 的了 树状数组 对于序列a 我们设一个数组cc i a i 2 k 1 a i k为i在二进制下末尾0的个数2 k就是i保留最右边的1 其余位全变0i从1开始算 c即为a的树状数组对于i 如何求2 k 通常我们用lowbit x 表示x对应的2klowbit x x x c i a i lowbit i 1 a i c1 a1c2 a1 a2c3 a3c4 a1 a2 a3 a4c5 a5c6 a5 a6c7 a7c8 a1 a2 a3 a4 a5 a6 a7 a8 c16 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 图示 设sum k a 1 a 2 a k 则a i a i 1 a j sum j sum i 1 根据c的构成规律 可以发现sum k 可以表示为 sum k c n1 c n2 c nm 其中nm kni 1 ni lowbit ni ni lowbit ni 是什么样子 就是ni的二进制去掉最右边的1k的二进制里最多有几个1 log2k 向上取整 个sum k 最多log2k 向上取整 项 所以本次求和的复杂度就是log2k 如果a i 更新了 那么以下的几项都需要更新 c n1 c n2 c nm 其中 n1 i ni 1 ni lowbit ni 同理 总的来说更新一个元素的时间 也是logn的 a i 更新 c i 必须更新c i 更新 c i lowbit i 必须更新 c i lowbit i a i lowbit i lowbit i lowbit i 1 a i lowbit i 证明i lowbit i lowbit i lowbit i 1 i 就证明c i lowbit i 要更新lowbit i 显然比lowbit i lowbit i 要小所以i lowbit i lowbit i lowbit i 1 i 下面要证明 若c i 更新 则对任何k i k i lowbit i c k 都不需要更新 即c k 不包含a i c k a k lowbit k 1 a k 只要证明k lowbit k 1比i大即可因i k i lowbit i 假设i的最右边的1是从右到左从0开始数的第n位 那么i lowbit i 就是将i的低n位全变成1后 再加1 那么k一定是从第n位到最高位都和i相同 但是低n位比