线段树：竞赛数据结构的基石

无论是纯粹的数据结构题还是数据结构优化其他算法，线段树都是绕不开的一个东西。

线段树的基本思想事实上十分简单：分治。把大区间拆成小区间，能延迟操作就延迟操作，这就是线段树的基本思想。它解决的问题也很简单：区间查询，区间修改。

在数据结构题以外，我们依然可以见到线段树的身影，包括但不限于树剖维护树上问题、优化dp状态转移、优化dijkstra等。这些我们都将在下面见到例题。

当然，在面对一些其他问题时，线段树的功能就有些捉襟见肘了，这种时候我们通常会考虑另一个几乎万能的数据结构：平衡树。当然平衡树也不是真的万能，有些问题（例如在线带修改区间第k大）单独的平衡树和线段树都无法解决，于是我们又会请出重量级的数据结构：树套树。不过，这些都超出了我们现在的讨论范围。这篇文章的重心依然会放在线段树上。

关于树链剖分

首先，需要知道一个事情：树链剖分其实很简单。

其次，需要知道另一个事情：树链剖分能解决的只有静态树上问题。如果你需要解决动态树（指的是树的结构发生变化）的问题，那么你需要的应该是Link-Cut Tree

那么树剖可以解决什么问题呢？

事实上，单单一个树剖能解决的问题不多，但是由于树剖的一些优秀性质，使得我们可以通过树剖+数据结构（例如线段树）的方式，实现：

什么是二叉搜索树？

讲二叉搜索树之前，首先得知道他解决了什么问题：

1. 查找数列第k大
2. 查询一个数的排名rank
3. 插入一个数
4. 删除一个数

显然，一个每次操作后都sort一遍的数组就可以解决这个问题。但是这显然不是我们想要的答案：他太慢了。

那么有什么快一些的方案呢？有，就是二叉搜索树 Binary Search Tree。

首先，顾名思义，二叉搜索树首先是一棵二叉树。