PDF《高级数据结构》

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 高级数据结构 wzj52501 Peking University

2018 年10 月22 日wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 前言 数据结构作为计算机科学重要的一个分支,在信息学竞赛中也有着广 泛的应用. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 前言 数据结构作为计算机科学重要的一个分支,在信息学竞赛中也有着广 泛的应用. 熟练掌握并应用数据结构知识,是在 NOI 等高水平比赛中制胜的关键 一环. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Part.1 树状数组 wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fenwick Tree 树状数组在竞赛中是一种主要用来实现以下操作的数据结构. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fenwick Tree 树状数组在竞赛中是一种主要用来实现以下操作的数据结构. 维护一个长度为 n 的数组,要求支持

2 种操作.

1 更改一个位置的权值 Ax = v.

2 询问前缀和 ∑x i=1 Ai. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fenwick Tree 树状数组在竞赛中是一种主要用来实现以下操作的数据结构. 维护一个长度为 n 的数组,要求支持

2 种操作.

1 更改一个位置的权值 Ax = v.

2 询问前缀和 ∑x i=1 Ai. 两种操作的时间复杂度均为 O(log n). wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 原理 ∑15 i=1 Ai = C(15) + C(14) + C(12) + C(8) wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 优劣 树状数组支持的操作确实被线段树完全包含: ( wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 优劣 树状数组支持的操作确实被线段树完全包含: ( 树状数组简单好写,高效便捷. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 优劣 树状数组支持的操作确实被线段树完全包含: ( 树状数组简单好写,高效便捷. 值得一提的是,树状数组可以维护前缀最值和单点更新(形如 Ax = max(Ax, v)) ,另外也经常作为嵌套数据结构的第一层. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

1 矩形数点 给定 n 个点的坐标 (xi, yi),你需要回答 q 次询问.每次询问给出了一 个以 (x1, y1) 为左上角,(x2, y2) 为右下角的矩形,你需要回答被这个 矩形包含的点(可以在矩形边界上)的个数. n, q ≤

105 ,

0 ≤ xi, yi ≤

109 ,

0 ≤ x1 ≤ x2 ≤

109 ,

0 ≤ y1 ≤ y2 ≤

109 wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

1 矩形数点 给定 n 个点的坐标 (xi, yi),你需要回答 q 次询问.每次询问给出了一 个以 (x1, y1) 为左上角,(x2, y2) 为右下角的矩形,你需要回答被这个 矩形包含的点(可以在矩形边界上)的个数. n, q ≤