前言

线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。线段树具有以下性质：

  1. 线段树的每个结点代表一个区间；
  2. 线段树的每个叶结点代表一个长度为1的区间；
  3. 线段树的每个非叶结点代表一个长度大于1的区间；
  4. 线段树的每个非叶结点的左子树代表一个左半区间，右子树代表一个右半区间；

拥有这种性质的搜索树，时间复杂度是O(logn)，所以线段树是一种高效的数据结构。

这里，我们用数组来表示线段树，其中数组下标代表结点编号，结点下标为i的结点，其左子结点下标为2i+1，右子结点下标为2i+2。

本文子问题是记录区间最小值，所以线段树结点中存储的是区间最小值。

线段树的构建

线段树的构建过程如下：

  1. 确定线段树的深度，即log2(n)向上取整；
  2. 创建线段树，每个结点包含一个区间和两个子结点；

代码

1
2
3
4
5
6
7
8
9
10
void build(vector<int> &arr, int start, int end, int id) {
    if(start == end) {
        tree[id] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(arr, start, mid, 2 * id + 1);
    build(arr, mid + 1, end, 2 * id + 2);
    tree[id] = fmim(tree[2 * id + 1] , tree[2 * id + 2]);
}

线段树的更新

线段树的更新过程如下：

  1. 找到需要更新的结点；
  2. 更新结点的值；
  3. 更新父结点的值；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void update(int start, int end, int id, int index, int val) {
    if(start == end) {
        tree[id] = val;
        return;
    }
    int mid = (start + end) / 2;
    if(index <= mid) {
        update(arr, start, mid, 2 * id + 1, index, val);
    } else {
        update(arr, mid + 1, end, 2 * id + 2, index, val);
    }
    tree[id] = fmim(tree[2 * id + 1] , tree[2 * id + 2]);
}

线段树的查询

线段树的查询过程如下：

  1. 找到需要查询的区间；
  2. 查询区间内的最小值；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int query(int start, int end, int id, int L, int R) {
    if(L <= start && end <= R) {
        return tree[id];
    }
    int mid = (start + end) / 2;
    int res = INT_MAX;
    if(L <= mid) {
        res = fmim(res, query(arr, start, mid, 2 * id + 1, L, R));
    }
    if(R > mid) {
        res = fmim(res, query(arr, mid + 1, end, 2 * id + 2, L, R));
    }
    return res;
}

总结

这里是基本的线段树算法，如果需要更复杂的操作，可以在此基础上进行扩展。这里暂不赘述。