acpty/dsrw

Part I 10pts

熟悉你的框架

对于一个基本数据结构，我们一定会涉及以下四个部分：增、删、查、改，对于 B+ 树也不例外。为了减少大家的工作量，我们引入了一套非常优秀的框架，框架已经正确地实现了这些基本功能。不过，在增加新功能之前，我们希望你们尽可能熟悉这套框架的内容，包括但不限于接口的使用等。因此，第一个部分主要需要完成 main 函数中的测试，并利用 point query 实现最简单的 range query。

具体来说，框架的作者提出了一些测试数据，你们需要实现 main.cpp 文件，读取测试数据，调用相关接口完成计算，然后按照规定输出结果。另外，查询操作分为两大类：点查询（point query）与范围查询（range query），一种最简单的 range query 的实现即为很多个 point query，在这个部分可以使用这种 brute force 的策略实现 range query。

具体来说，你需要在 main.cpp 中通过以下测例：

第一行为四个整数 n m p q

后面 n 行每行为一个 kv 对，保证 key 不重复，需要插入 map 中

接下来有 m 个点查询，每行给定一个 key，若存在则输出对应的 value，否则输出 NOT FOUND

然后 p 行每行为一个 kv 对，需要在 map 中更新，保证每个 key 都曾被插入过

接下来有 q 个范围查询，每行给定 lvalue 与 rvalue，请输出在 [lvalue, rvalue) 中出现的 key 的个数

输入保证所有数据均为 int 类型

（测试样例待补充，不卡性能）

---

Part II 50pts

更加高效的范围查询

在 Part II 中我们熟悉了 B+ 树的代码框架与基本接口使用，并用非常原始的方式实现了范围查询。这很简单，但也确实非常低效。如果在中间节点存储相关信息，是否可以避免很多深入遍历的过程？请思考如何在结点上维护额外的信息，从而大幅增加 range query 的效率。注意你可能需要仔细观察框架中增删改的操作，结点中的额外信息在很多部分都要额外维护。

我们会从正确性、性能和设计思路的方面进行评价。

请改进你的程序，使之通过以下测例：

第一行为两个整数 n m

后面 n 行每行为一个 kv 对，key 可能出现重复

接下来有 m 个范围查询，每行给定 lvalue 与 rvalue，请输出在 [lvalue, rvalue) 中出现过 key 的个数

输入保证所有数据均为 int 类型

（测试样例待补充，加入性能要求）

---

Part III 40pts

性能调优

在Part II中大家已经实现了自己的range query，下面我们来做些具体任务吧！

任务描述

1. 实现学生信息类，包含如下属性

   a) 学生学号

   b) 学生姓名

   c) 学生性别

   d) 现实生活中的数据结构课程成绩

2. 生成 1M 个上述对象。

3. 利用 B+ 树，对现实生活中的数据结构课程的成绩建立索引（插入 B+ 树），注意这里的成绩可能会相同，因而在处理的时候需要适当修改代码。

4. 利用 range query，sampling，point query 的方式，大致得到成绩分布

   a. Sampling：对成绩采样，用采样出的成绩分布近似估计整体分布

   b. Range query：将成绩切分成5分/10分等长度自定的区间，具体查询这个区间内成绩出现的频数，进而估计整体分布。

   c. 绘制各个分数段频率图像，根据图像近似估计成绩的25,50,75分位数

5. Tips

   a. 评分将首先看三个分位数是否正确，再根据运行时间打分

   b. 显然，sampling 最快最不准，range query 其次，point query 最慢最准，先 sampling 大概估计整体分布，再确定不同区间下，range query 的区间长度，最后进行 point query 确定分位数是一种折中策略