线段树（Segment Tree）是一种数据结构，它主要用于维护区间信息（要求满足结合律），它可以实现 𝑂(log⁡𝑛) 的区间修改，还可以同时支持多种操作（加、乘）。从数据结构的角度来说，线段树是用一个完全二叉树来存储对应于其每一个区间（segment）的数据。该二叉树的每一个结点中保存着相对应于这一个区间的信息。同时，线段树所使用的这个二叉树是用一个数组保存的，与堆（Heap）的实现方式相

有N件物品和一个最多能被重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。这是标准的背包问题，一开始我们可以尝试暴力的解法，每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。所以暴力的解法是指数级别的时间复杂度。进而才需要动

在计算几何中，扫描线算法（scan line algorithm）一般用来解决几何图形的面积交并，周长交并问题，扫描线算法的核心思想是利用扫描线（通常是水平线或垂直线）在几何空间中“扫描”对象，以确定哪些对象与扫描线相交。下面我们就来通过求矩形的面积并来介绍扫描线算法。先来看看怎么求下面图形的面积并：传统算法是两个矩形面积相加减去重合的面积：但是这样算非常的耗费时间，因为每个矩形都需要两两配对，查

（１）计算已知类别数据集中的点与当前点之间的距离；（２）按照距离递增次序排序；（３）选取与当前点距离最小的k个点；（４）确定前k个点所在类别的出现频率；（５）返回前k个点出现频率最高的类别作为当前点的预测分类。