线段树（数组实现）

简介

线段树是一种用于处理区间查询和更新问题的数据结构。其关键思想在于使用树中的一个节点表示一个区间的信息，父节点表示的区间从中间位置划分为两个子节点表示的区间。用[l,r][l,r]表示要查询/更新的区间，[s,e][s,e]表示树中的某个节点表示的区间，当前者完全包括了后者时，说明本次操作可以直接通过对某个单一节点操作完成。在完成操作后，在递归的”归“过程中更新查询结果/父节点的信息，直到根节点。

image-20240709164140477

可以直接用数组存储这棵树，根节点存储在下标1处，对于下标为id的当前节点，其左孩子的下标为2*id，右孩子的下标为2*id+1。

模板

为什么数组要开四倍空间：最理想情况即满二叉树时， 区间长度为1的叶子节点全部位于最底层，此时线段树中节点总数为2n−12n-1；对于一般情况如上图，底层节点数应为大于等于n的最小的二次幂，总节点数应为:

2⌊log2n⌋+1∗2−12^{\lfloor{log_2 n}\rfloor + 1}*2-1

基于数组的线段树实现如下，直接在已知原数组的基础上建立线段树（即单点更新）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n = arr.length;
int[] seg = new int[4*n];
build(1, 1, n, arr);	// 线段树的根节点下标以及arr的起始下标都为1

public void build(int node, int l, int r, int[] arr){
    if(l == r){
        seg[node] = arr[l-1];
        return;
    }
    int m = (l+r) >> 1;
    build(2*node, l, m, arr);
    build(2*node+1, m+1, r, arr);
    seg[node] = Math.max(seg[2*node], seg[2*node+1]);
}

线段树（动态开点+懒更新）

简介

动态开点：对于数据分布比较稀疏的情况，基于数组的线段树可能会爆内存，这时可以使用Node形式实现线段树，采用动态开点策略，即只有要用到某节点时才新建该节点。

懒更新：懒更新策略即当树中节点表示的线段完全被当前操作区间包含时，无需继续向下递归，而是使用一个lazyMark将其标记，直到下方节点被真正使用时才使用lazyMark进行更新。如果线段树不采用懒更新策略，那么只有单点更新操作是O(logn)的，因为每次区间更新时，最坏的情况（例如更新根节点的值）需要遍历所有树中节点。

模板

以求区间最大值为例：

  1. 区间[l,r]代表要操作的区间，它在一次调用期间是永远不会被更改的

  2. 如果操作区间包含了当前区间[s,e]，那么更新/返回最大值

  3. 如果操作区间与当前区间的左半有交集，那么进入到左侧线段；如果与右半有交集，那么进入到右侧线段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * 线段树的Node形式实现，动态开点、懒更新
 * 下面的算法实现的是区间最小值的维护和查询
 */
class Node {
    int val = Integer.MAX_VALUE;
    int lazyMark = Integer.MAX_VALUE;
    Node left;
    Node right;
    Node(){}
    Node(int v){
        this.val = v;
    }
}

class SegTree {
    public Node root = new Node();

    // 查询区间[l, r]的最小值
    int query(Node node, int l, int r, int s, int e){
        if(l <= s && e <= r) return node.val;
        int m = (s+e)>>1, ret = Integer.MAX_VALUE;
        pushdown(node);
        if(l <= m) ret = Math.min(ret, query(node.left, l, r, s, m));
        if(m+1 <= r) ret = Math.min(ret, query(node.right, l, r, m+1, e));
        return ret;
    }

    // 用v尝试更新区间[l, r]的最小值
    void update(Node node, int l, int r, int s, int e, int v){
        if(l <= s && e <= r){
            node.val = Math.min(node.val, v);
            node.lazyMark = Math.min(node.lazyMark, v);
            return;
        }
        pushdown(node);
        int m = (s+e)>>1;
        if(l <= m) update(node.left, l, r, s, m, v);
        if(m+1 <= r) update(node.right, l, r, m+1, e, v);
        node.val = Math.min(node.left.val, node.right.val);
    }

    void pushdown(Node node) {
        // 检查左右子节点是否为 null，如果是，需要创建一个新的子节点。
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if(node.lazyMark == Integer.MAX_VALUE) return;
        // 如果当前节点具有有效的 lazyMark 值，则将其传递给子节点。
        node.left.val = Math.min(node.left.val, node.lazyMark);
        node.right.val = Math.min(node.right.val, node.lazyMark);
        node.left.lazyMark = Math.min(node.left.lazyMark, node.lazyMark);
        node.right.lazyMark = Math.min(node.right.lazyMark, node.lazyMark);
        node.lazyMark = Integer.MAX_VALUE;
    }
}

线段树二分

在使用线段树得到了各个区间的信息后，可以利用这些信息进行二分。
例如本题2940. 找到 Alice 和 Bob 可以相遇的建筑 ，对于每个查询，查找满足 i > L 且 heights[i] > v的最小的下标 i ，这个查询可以使用线段树二分，线段树维护区间最大值，单次O(logn)的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int query(int o, int l, int r, int L, int v) {
    if (v >= mx[o]) { // 最大值 <= v，没法找到 > v 的数
        return 0;
    }
    if (l == r) { // 找到了
        return l;
    }
    int m = (l + r) / 2;
    if (L <= m) {
        int pos = query(o * 2, l, m, L, v); // 递归左子树
        if (pos > 0) { // 找到了
            return pos;
        }
    }
    return query(o * 2 + 1, m + 1, r, L, v); // 递归右子树
}

题单

§线段树（无区间更新）

子数组中占绝大多数的元素 2205

最长递增子序列 II 2280

找到 Alice 和 Bob 可以相遇的建筑 2327 线段树二分

以组为单位订音乐会的门票 2470 线段树二分

由单个字符重复的最长子字符串 2629

§Lazy 线段树（有区间更新）

完成所有任务的最少时间 2381

更新数组后处理求和查询 2398

奇妙序列 2476 有更简单的做法

子数组不同元素数目的平方和 II 2816
LCP 05. 发 LeetCoin
LCP 27. 黑盒光线反射

§ 动态开点线段树

部分题目也可以用珂朵莉树解决。

掉落的方块

Range 模块

我的日程安排表 I

我的日程安排表 II

我的日程安排表 III

矩形面积 II

统计区间中的整数数目 2222

达到末尾下标所需的最大跳跃次数

__END__