Segment Tree
线段树¶
线段树即树的每个节点表示线段，方便区间查询、修改等操作
线段树节点存储内容可以根据需要自定义，以及在范围确定的情况下，不用在节点中存储节点的范围
建立¶
为了速度基本都会开一个数组来存储节点，从节点1开始作为根节点，之后左右孩子的访问方式就是
- rank * 2
- rank * 2 + 1
方法一
根据叶节点的位置不同，有两种建立方法，一种是把线段树补成一棵完全二叉树，即本来有N个点，要找刚大于其的2的整数次幂TREE_N，然后从1到TREE_N-1作为内部节点，TREE_N到TREE_N+N-1来存储数据
代码如下，先找到TREE_N，然后存储叶节点，然后从下往上来更新区间信息
这种建立方式，查询一定是从[1, TREE_N]开始，而不是从[1, N]开始
void build(vector<Segment>& tree, const vector<int>& arr) {
int nodesNum = 1, length = arr.size();
while (nodesNum < length) nodesNum *= 2;
tree.assign(nodesNum * 2, Segment());
for (int i = 0; i < length; i ++) {
tree[nodesNum + i].num = arr[i];
tree[nodesNum + i].cnt = 1;
}
for (int i = nodesNum - 1; i >= 1; i --)
tree[i].join(tree[i * 2], tree[i * 2 + 1]);
}
方法二
方法二就是从上往下来递归建立，这样有些叶子节点不用存储在最底层，而是可以存储在之前内部节点的位置
但其实两种建立方式所需大小差不多，只要是用数组来访问的形式，都是这样的结果