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