image.png
问题1：线段树为什么要开4n 空间
核心功能
1、线段树的存储
每个节点包含三个域 l、r、mx 表示[l,r]区间的最值 ,线段树除了最后一层，其他层构成一个满二叉树，因此采用顺序存储的方式
image.png
static class Node{
int l, r, mx;
}
1、build--创建线段树--递归的方式创建
- 如果是叶子结点(l == r)，那么节点的最值就是对应的位置的元素的值
- 如果非叶子结点，则递归创建左子树和右子树
- 节点的区间最值等于该节点左右子树的最大值
//递归创建线段树，k表示存储的下标，区间[l,r]
static void build(int k, int l, int r){
tree[k].l = l;
tree[k].r = r;
//1、如果是叶子节点
if(l == r) {
tree[k].mx = a[l];
return;
}
//2、 递归
int mid = (l + r) >> 1;
//2.1、递归左子树
build(l << k, l, mid);
//2.2 递归右子树
build(l << k | 1, mid + 1, r);
//3、回归合并的时候更新节点的值--类似于归并排序
pushup(k);
}
2、pushup
//回归的时候 使用左右子节点 来更新当前节点
static void pushup(int k){
tree[k].mx = Math.max(tree[k << 1].mx, tree[k << 1 | 1].mx);
}
3、点更新--修改一个元素的值，a[i] = v
算法步骤：
点更新
- 若是叶子节点，满足l = r 且 l = i, 则修改此节点的最值为 v
- 如果是非叶子节点，则判断是在左子树中更新还是右子树中更新
- 返回时更新节点的最值
//点更新，将a[i] 修改为v
static void update(int k, int i, int x){
if(tree[k].l == tree[k].r && tree[k].l == i){
//说明找到了点
tree[k].mx = v;
return;
}
//2、 递归修改
int mid = tree[k].l + tree[k].r >> 1;
//2.1 递归左子树
if(i <= mid) update(k << 1, i, x);
//2.2 递归右子树
else update(k << 1 | 1, i, x);
//2.3 回归更新最值
pushup(k);
}
4、query1--区间覆盖（要查找的区间一直不变）
- 若节点所在的区间被查询区间[l,r]覆盖，则返回改节点的最值
- 判断是在左子树 还是右子树
-
返回最值
区间覆盖--求区间最大值
5、query2--区间相等 (要查找的区间 一直在变小)
算法分析
- 树高 O(logn)
- 查询和更新的时间复杂度都是 O(logn)
- 空间复杂度是O(n);
- 线段树主要是用于更新和查询，一般至少有一个是区间更新和查询
练习
image.png
