数据结构课件线段树.pdf

线段树 上海交通大学 方泓杰 线段树基础1 有一个个数的序列{ }，要求实现三种操作： 1. 将 改为； 2. 将 加上； σ 3. 查询 的值。 = 1 ≤, ≤ 105 线段树基础2 有一个个数的序列{ }，要求实现两种操作： 1. 将 ≤ ≤ 加上； σ 2. 查询 的值。 = 1 ≤, ≤ 105 打标记/ 标记永久化 线段树基础3 有一个个数的序列{ }，要求实现三种操作： 1. 将 ≤ ≤ 改为； 2. 将 ≤ ≤ 加上； σ 3. 查询 的值。 = 1 ≤, ≤ 105 线段树基础4 有一个个数的序列{ }，要求实现四种操作： 1. 将 ≤ ≤ 改为； 2. 将 ≤ ≤ 加上； 3. 将 ≤ ≤ 乘上； σ 4. 查询 的值。 = 1 ≤, ≤ 105 标记的顺序与下传 线段树基础5 有一个个数的序列{ }，要求实现两种操作： 1. 令 = （ ≤ ≤） σ 2. 查询 的值。 = 1 ≤, ≤ 105 标记的顺序与下传 Copying Data 对于数组和数组，长度均为，有个操作，操作有两种： 1. 将中从开始的连续个元素覆盖掉中从开始的连续个元素。 2. 求 的值； 1 ≤, ≤ 105 CodeForces 292E Copying Data 对建立线段树，线段树每个节点存 , 。 表示这个节点所代表的b的区间被a 中的, 覆盖了。 相当于打标记操作。 时间复杂度 log Ball 有个人，每个人有三个属性 , , 。 如果一个人的三个属性均小于另一个人的，那么他将告辞。 问最后有多少人告辞。 1 ≤ ≤ 5 ×105 CodeForces 12D Ball 三维偏序？ 树套树？ 分治？ 其实，只要线段树就够了！ 首先将第一维离散化，第二维从大到小排序，以第一维为坐标在线段树中插入第三维的值。 由于逐个插入，第二维一定递减； 对于每个新插入的数只要保证他插入位置后面的区间最大值比这个数小就不会告辞。 时间复杂度 log XOR on segment 给出个数 , , …, ，个操作，操作有两种： 1 2 1. 将 , , …, 同时异或； +1 2. 求 + + ⋯+ 。 +1 5 4 6 1 ≤ ≤ 10 , 1 ≤ ≤ 5 ×10 , 1 ≤ ≤ 10 CodeForces 242E XOR on segment 区间异或不太好直接维护，于是我们考虑将所有数二进制分解。 我们把每一位单独提出来做，那么对于每一位，异或