1.树状数组->「单点修改 & 区间查询」：

先输入一个长度为n的数组nums，有如下两种操作：

1.输入一个数m，输出数组中下标1~m的前缀和sum[1,m]

2.对某个指定下标的数进行值的修改

p10

常规方法：前缀和，但是当单点修改的次数增多，前缀和更新耗时O(N)，然后再求sum[1,m]，总体时间复杂度为O(N^2)

进阶方法：树状数组和线段树可以达到单次操作logN级别。平均时间复杂度O(NlogN)

p11

7=0111=0100+0010+0001=lowBit(7)+lowBit(3)+lowBit(1)

前置知识：二进制区间分解lowBit(x)=x^(-x)求出x中仅保留最低位的1的数值，lowBit(7)=0100=4

1
2
3
int lowbit(int x) {
    return x & -x;
}

概念：树状数组就是一种基于二进制思想的数据结构，基本用途是维护序列的前缀和。

对于给定的序列a，设树状数组为c，则c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和

1
int[] tr = new int[n];

主要有以下两个基本操作:

(1) update，单点修改，修改序列a中的某个元素;

(2) query，区间查询，查询序列a中区间[1,x]的所有数的和。

p12

操作1:区间查询query

树状数组能够完成的是查询前缀和，相减即可得到区间和。

利用c[x]维护的是序列a中[x-lowbit(x)+1,x]的区间和，然后不断向前寻找即可，时间复杂度为O(logN)。

1
2
3
4
5
int query(int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
    return ans;
}

操作2:单点修改update

单点修改更准确的说是“单点增加”，给序列a中的一个数a[x]加上t，然后要更新树状数组c维护的前缀和，只需要不断向上维护c[x]的父亲结点即可，时间复杂度为O(logN)。

1
2
3
void add(int x, int u) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
}

注意：这里都默认索引从1开始

思考:如何初始化树状数组?

方法一:输入序列a等价于对a进行单点修改，更新树状数组即可，时间复杂度为O(NlogN)。

1
2
3
for (int i = 0; i < nums.length; i++) {
    add(i, 1);
}

方法二:考虑每个结点对父亲结点的贡献，时间复杂度为O(N)。

1
2
3
4
for (int i = 0; i < nums.length; i++) {
    tr[i] += nums[i];
    if (i + lowBit(i) <= n) tr[i + lowBit(i)] += tr[i];
}

三叶姐树状数组模板：

一篇不错的图解：[树状数组] 详解树状数组, 包含更新查询图解, 秒懂lowbit含义(JAVA 65ms, 68.6MB)

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
// 上来先把三个方法写出来
{
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    // 查询前缀和的方法
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
}

// 初始化「树状数组」，要默认数组是从 1 开始
{
    for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}

// 使用「树状数组」：
{   
    void update(int i, int val) {
        // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - nums[i]
        add(i + 1, val - nums[i]); 
        nums[i] = val;
    }
    
    int sumRange(int l, int r) {
        return query(r + 1) - query(l);
    }
}

2.线段树「单点修改、区间修改、单点查询、区间查询->但性能不高」

参考资料：https://mp.weixin.qq.com/s/T3Ds8Eb8mZ5f96NjRFr6WA

以下笔记均参考力扣题解(推荐)：Range模块【线段树动态开点+线段树图解】

什么是线段树？

线段树其实是一种二叉搜索树，将一个大的区间划分为一个个单元区间。

内个单元区间表示成一个节点(单元区间->节点) 线段树中的线段，其实也是区间的意思，就是区间树

假设我们有一个数组为[1,2,3,4,5,6,7,8]，我们表示为一个区间和线段树就是下图：

p13

可见线段树的区间是按照区间的中点进行分叉，左子节点的区间必定小于右子节点的区间，同理左右子树均是BST

构建线段树代码（val基于区间求和）：

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
/**
 * @author Fomalhaut
 * @date 2022/6/22
 * @desc 线段树模板(今天一定一定要写出来!!!!!)
 */
public class SegmentTree {
    // 用节点数组表示的线段树
    Node[] tree;
    // 原始数据
    int[] data;

    // 初始化线段树
    public SegmentTree(int[] data) {
        this.data = data;   // 载入数据
        this.tree = new Node[4 * data.length];  // 节点个数统一开4*N个
    }

    /*
        线段树节点类
         */
    static class Node {
        int left;   // (该节点对应的)区间左端点
        int right;  // 区间右端点
        int lazy;   // 懒标记
        int val;    // 节点值(根据不同的问题意义不同)
    }

    /*
    根据区间左右边界[l,r]来构建线段树:idx表示线段树的节点索引,l与r分别表示区间左右边界
     */
    public void build(int idx, int l, int r) {
        tree[idx] = new Node(); // 创建idx位置的节点
        tree[idx].left = l; // 该节点左边界为l
        tree[idx].right = r;    //该节点右边界为r
        // base case:到达叶子结点直接赋值
        if (l == r) {
            tree[idx].val = data[r - 1];    // 因为idx从1开始,区间的l与r也是从1开始,但是data索引从0开始,因此向左偏移1位
        }
        int mid = l + (r - l) / 2;  // [l,r]区间中点
        // 递归构建左右子树:当idx索引从1开始时,idx*2为左子节点,idx*2+1为右子节点
        build(idx * 2, l, mid); // 左子节点区间范围[l,mid] 左子节点个数>=右子节点
        build(idx * 2 + 1, mid + 1, r); // 右子节点区间范围[mid+1,r]
        tree[idx].val = tree[idx * 2].val + tree[idx * 2 + 1].val;  // 更新idx节点的值
    }
}

懒标记的引入：

p14

如果是线段树，我们直接对根节点的值进行+(8-1+1)*1的操作就可以得到新的区间和，但是这样当我们查询中间某段区间的和时就会发现不对，因为这个+(8-1+1)*1没有涉及根节点的区间和操作！

于是就想可不可以在root处引入一个标记的量，在我们要下探到要求root子区间的区间和时可以把这个+1操作带下去？把子区间进行更新？于是就引入了lazy字段

注意： 我们只有在用到没有更新的区间时（也就是当前区间含有lazy），才会下传lazy，达到懒更新的目的。

p15

p16

也许我们还会更新[5,8]区间的值，我们除了设置lazy字段外，还需要将结果上传到他的父节点！（很显然，下面变了，上面区间包含下面也要变）

p17

p18

更新与查询代码如下（非动态开点）：

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
56
57
58
59
60
/*
更新某个区间的值:idx为节点索引,[l,r]为要更新的区间,val代表要更新进去的值
 */
public void update(int idx, int l, int r, int val) {
    // idx节点区间在要修改的[l,r]区间里面->直接更新到这里并并进行懒标记即可
    if (tree[idx].left >= l && tree[idx].right <= r) {
        // idx节点值 += val * idx节点区间的的节点数
        // 意思就是更新了idx节点的整个区间,节点值就加上相应的数
        tree[idx].val += (tree[idx].right - tree[idx].left + 1) * val;
        // 对idx节点进行懒标记
        tree[idx].lazy = val;
        return; // 结束
    }
    if (tree[idx].lazy != 0) pushDown(idx); // 当前节点有懒标记->下沉懒标记
    // [l,r]与idx节点左区间有交集
    if (l <= tree[idx * 2].right) update(idx * 2, l, r, val);
    // [l,r]与idx节点右区间有交集
    if (r >= tree[idx * 2 + 1].left) update(idx * 2 + 1, l, r, val);
    // 底下递归完成后向上回溯更新idx的值
    pushUp(idx);
}

/*
查询区间[l,r]
 */
public int query(int idx, int l, int r) {
    int res = 0;
    // idx节点的区间被[l,r]完全包含 -> 直接返回节点值
    if (tree[idx].left >= l && tree[idx].right <= r) return tree[idx].val;
    // 否则就还要继续往下走更小的区间
    // 遇到有懒标记也要下沉(因为你现在要查询小区间的信息)
    if (tree[idx].lazy != 0) pushDown(idx);
    // 跟左右区间有交集
    if (tree[idx * 2].right >= l) res += query(idx * 2, l, r);  // 累加递归完成的值
    if (tree[idx * 2 + 1].left <= r) res += query(idx * 2 + 1, l, r);
    return res; // 返回结果
}

/*
上传结果
 */
public void pushUp(int idx) {
    tree[idx].val = tree[idx * 2].val + tree[idx * 2 + 1].val;
}

/*
下沉懒标记
 */
public void pushDown(int idx) {
    // 向左右子节点下沉lazy(累加而不是覆盖)
    tree[idx * 2].lazy += tree[idx].lazy;
    tree[idx * 2 + 1].lazy += tree[idx].lazy;
    // idx节点区间的中点
    int mid = tree[idx].left + (tree[idx].right - tree[idx].left) / 2;
    // 左右子节点的节点值分别加上(懒标记的值*区间节点个数)
    tree[idx * 2].val += tree[idx].lazy * (mid - tree[idx].left + 1);
    tree[idx * 2 + 1].val += tree[idx].lazy * (tree[idx].right - mid);
    // 下沉了lazy后idx的懒标记置0
    tree[idx].lazy = 0;
}

动态开点的引入：

上述代码只是针对不对区间长度进行修改，只能在固定的区间内查询和修改，并且用到了4n的空间，有些空间根本没有被使用，有的题目数据规模到了1e9，如果我们开4n的空间并不可行！

于是我们需要动态地进行节点创建，即我们不用idx * 2和idx* 2 + 1来表示节点的左右子节点，而是在Node里添加leftChild和rightChild两个引用，来找到左右节点。由于我们是在更新与查询中进行动态开点，所以不需要build树！

动态开点的代码如下：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
 * @author Fomalhaut
 * @date 2022/6/23
 * @desc 线段树(动态开点+懒标记)
 */
public class SegmentTree_Dynamic {
    /*
    动态开点线段树节点类
     */
    static class Node {
        int left, right;    // 区间左右端点
        int val;    // 节点的值
        int lazy;   // 懒标记:0代表没有懒标记
        Node leftChild, rightChild; // 左右子树引用

        // 根据区间[left,right]创建节点
        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    /*
    动态开点的区间更新:root代表根节点,[l,r]代表更新区间,val代表更新的值
     */
    public void update(Node root, int l, int r, int val) {
        // 1.[l,r]不在root区间的范围内 -> 直接返回
        if (r < root.left || l > root.right) return;
        // 2.[l,r]包含root区间 -> 进行懒标记并更新root的值
        if (root.left >= l && root.right <= r) {
            root.lazy = val;    // 进行懒标记
            root.val += (root.right - root.left + 1) * val; // 节点值+=区间长度*val
            return;
        }
        // 3.继续往下走
        lazyCreate(root);   // 动态开点
        pushDown(root); // 下传lazy
        update(root.leftChild, l, r, val);  // 更新左子树区间
        update(root.rightChild, l, r, val); // 更新右子树区间
        pushUp(root);   // 上传结果
    }

    /*
    动态开点的查询区间[l,r]
     */
    public int query(Node root, int l, int r) {
        // [l,r]必定在root里面,因为root是最大的可能区间
        // 1.root的区间在[l,r]里面 -> 直接返回节点值
        if (root.left >= l && root.right <= r) return root.val;
        // 2.否则要往下走找到[l,r]完全包含子节点整个区间的情况
        lazyCreate(root);   // 动态开点
        pushDown(root); // 下传懒标记
        int mid = root.left + (root.right - root.left) / 2; // root区间中点
        // 左子树范围[ll, mid] 右子树范围[mid+1,rr]
        if (r <= mid) { // [l,r]只占据到root左子树
            return query(root.leftChild, l, r);
        } else if (l > mid) {   // [l,r]只占据到root右子树
            return query(root.rightChild, l, r);
        } else {    // [l,r]占据root左子树与右子树
            return query(root.leftChild, l, mid) + query(root.rightChild, mid + 1, r);
        }
        // 不用上传结果了因为查询不改变节点的值
    }

    /*
    上传结果
     */
    public void pushUp(Node root) {
        root.val = root.leftChild.val + root.rightChild.val;
    }

    /*
    下传懒标记:有懒标记->下传懒标记并更新子节点的值;没有->结束
     */
    public void pushDown(Node root) {
        // 当且仅当有懒标记才进行下传
        if (root.lazy != 0) {
            // 懒标记的值
            int v = root.lazy;
            // 懒标记下沉至左右子节点
            // 这里懒标记累加还是覆盖可以根据具体问题进行分析
            // 比如说是求区间的累加值就是+= 如果是只有两个状态那种可以直接进行覆盖(LC715.Range模块)
            root.leftChild.lazy += v;
            root.rightChild.lazy += v;
            // 更新左右子节点的值
            root.leftChild.val += (root.leftChild.right - root.leftChild.left + 1) * v;
            root.rightChild.val += (root.rightChild.right - root.rightChild.left + 1) * v;
            // root取消懒标记
            root.lazy = 0;
        }
    }

    /*
    创建左右子树
     */
    public void lazyCreate(Node root) {
        int mid = root.left + (root.right - root.left) / 2; // root区间中点
        // 创建左右子树并构建连接
        if (root.leftChild == null) root.leftChild = new Node(root.left, mid);
        if (root.rightChild == null) root.leftChild = new Node(mid + 1, root.right);
    }

数组表示的线段树(含懒标记+动态开点)可以参考三叶：

729. 我的日程安排表 I

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package leetcode.SegmentTree;

import org.junit.Test;

/**
 * @author Fomalhaut
 * @date 2022/6/24
 * @desc 729. 我的日程安排表 I
 */
public class Q729 {
    @Test
    public void test() {
        MyCalendar myCalendar = new MyCalendar();
        System.out.println(myCalendar.book(10, 20));    // true
        System.out.println(myCalendar.book(15, 25));    // false
        System.out.println(myCalendar.book(20, 30));    // true
    }

    class MyCalendar {
        /*
        本题是线段树的模板题之一,由于值域范围在[0,1e9]因此只能采用动态开点的方式,否则会出现MLE
        本题要动态地获当前区间是否完全被覆盖,可以将线段树节点值设为当前区间的节点数(叶子结点只有0与1的区间和)
        同时为了使查询的时间复杂度为严格的O(logN)要加入懒标记
        ->查询[start,end)区间是否能book就相当于求[start,end-1]的区间和是否为0
        懒标记的线段树空间复杂度为O(MlogN),M为操作次数; 查询和更新一次时间复杂度为:O(logN)
         */

        /*
         节点类:
         本节点与之前的模板不同,该节点成员没有显式地包含节点u的区间左右端点[lc,rc]
         区间左右端点[lc,rc]可以通过update()与query()显式地传入再进行递归计算
         */
        class Node {
            // ls 与rs 分别代表当节点的左右子节点在tr中的下标 (相当于leftChild与rightChild)
            // val 表示当前节点的区间和(只有0与1)
            // add为懒标记
            int ls, rs, add, val;
        }

        int N = (int) 1e9, M = 120010, cnt = 1; // N 区间范围; M 节点个数; cnt 节点索引
        Node[] tr = new Node[M];    // 数组表示的线段树

        public MyCalendar() {
            tr[0] = new Node(); // 根节点u从tr[0]开始
        }

        /*
        更新[l,r]区间的节点,更新值为val=1
        u 根节点索引;lc 与 rc 代表根节点u表示的值域范围
         */
        public void update(int u, int lc, int rc, int l, int r, int val) {
            // 节点u表示的范围[lc,rc]在[l,r]内部 -> 直接更新节点值和懒标记
            if (lc >= l && rc <= r) {
                tr[u].val = (rc - lc + 1) * val;
                tr[u].add = val;
                return;
            }
            lazyCreate(u);  // 动态开点
            pushDown(u, rc - lc + 1);   // 下传懒标记
            // 递归更新左右子节点
            int mid = lc + (rc - lc) / 2;
            if (l <= mid) update(tr[u].ls, lc, mid, l, r, val); // [l,r]占据到左子树
            if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, val);  // [l,r]占据到右子树
            pushUp(u);  // 回溯更新u的值
        }

        /*
        查询[l,r]区间的节点
        u 根节点索引;lc 与 rc 代表根节点u表示的值域范围
         */
        public int query(int u, int lc, int rc, int l, int r) {
            if (lc >= l && rc <= r) return tr[u].val;   // u节点区间在[l,r]内
            // 否则继续往下走
            lazyCreate(u);  // 动态开点
            pushDown(u, rc - lc + 1); // 下传懒标记
            int mid = lc + (rc - lc) / 2, res = 0;
            if (l <= mid) res = query(tr[u].ls, lc, mid, l, r); // [l,r]占据到左子树
            if (r > mid) res += query(tr[u].rs, mid + 1, rc, l, r);  // [l,r]占据到右子树
            return res; // 返回左右区间总和
            // 查询不更新端点的值因此不用回溯
        }

        /*
        向上更新u的值
         */
        public void pushUp(int u) {
            tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
        }

        /*
        下传懒标记
        其中 len 为节点表示的区间长度 用于简化计算区间长度
         */
        public void pushDown(int u, int len) {
            int v = tr[u].add;
            if (v != 0) {   // 只有懒标记不为0才下传
                // 1.下传懒标记
                tr[tr[u].ls].add = v;
                tr[tr[u].rs].add = v;
                // 2.更新子节点的值(不判断懒标记就要+=避免0覆盖)
                tr[tr[u].ls].val = (len - len / 2) * v; // 左(大)
                tr[tr[u].rs].val = (len / 2) * v;   // 右(小)
                // 3.懒标记下传完置0
                tr[u].add = 0;
            }
        }

        /*
        动态开点:动按需态创建左右子节点并构建连接
         */
        public void lazyCreate(int u) {
            if (tr[u].ls == 0) {    // 当且仅当左子节点没有时才进行开点(tr[u].ls为0表示还没开左子节点)
                tr[u].ls = cnt++;   // 构建与tr[u]的连接,索引依次取
                tr[tr[u].ls] = new Node();  // 开点
            }
            if (tr[u].rs == 0) {
                tr[u].rs = cnt++;
                tr[tr[u].rs] = new Node();
            }
        }

        public boolean book(int start, int end) {
            // 区间[start,end-1]已经有东西填充过了->不能book
            if (query(0, 0, N, start, end - 1) > 0) {
                return false;
            }
            // 否则更新并返回true
            update(0, 0, N, start, end - 1, 1);
            return true;
        }
    }
}

731. 我的日程安排表 II(注意节点维护的是最大值)

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package leetcode.SegmentTree;

import org.junit.Test;

/**
 * @author Fomalhaut
 * @date 2022/6/24
 * @desc 731. 我的日程安排表 II
 */
public class Q731 {
    @Test
    public void test() {
        MyCalendarTwo MyCalendar = new MyCalendarTwo();
        System.out.println(MyCalendar.book(10, 20));    // true
        System.out.println(MyCalendar.book(50, 60));    // true
        System.out.println(MyCalendar.book(10, 40));    // true
        System.out.println(MyCalendar.book(5, 15));     // false
        System.out.println(MyCalendar.book(5, 10));     // true
        System.out.println(MyCalendar.book(25, 55));    // true
    }

    class MyCalendarTwo {
        /*
        这题也可以用线段树进行求解:start与end的范围为[0,1e9]
        不过相比于Q729 我的日程安排表I 这里要维护的val为区间的最大值max
        当区间的最大值>=2就说明已经有两个重叠的预订,第3个预订就不能book了
        查询和更新一次时间复杂度为:O(logN) 空间复杂度为O(MlogN),M为操作次数
         */

        /*
        节点类
         */
        class Node {
            int ls, rs, add, max;   // ls, rs 为左右子节点在tr中索引(触手); add 懒标记; max 维护区间最大值
        }

        int N = (int) 1e9, M = 120010, cnt = 1; // N 区间范围; M 节点个数; cnt 节点在tr中的索引
        Node[] tr = new Node[M];

        public MyCalendarTwo() {
            tr[0] = new Node(); // 创建根节点
        }

        /*
        更新区间[l,r] 值为val
         */
        public void update(int u, int lc, int rc, int l, int r, int val) {
            // [l,r]在u表示的区间内
            if (lc >= l && rc <= r) {
                tr[u].add += val;   // 懒标记要累计(例如覆盖了2次)
                // 最大值是max(curVal,curVal+val)=curVal+val -> max += val;
                tr[u].max += val;
                return; // 结束
            }
            // [l,r]不在u内
            lazyCreate(u);  // 动态开点
            pushDown(u);    // 下传懒标记
            int mid = lc + (rc - lc) / 2;
            if (l <= mid) update(tr[u].ls, lc, mid, l, r, val); // 占据到左子树
            if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, val);  // 占据到右子树
            pushUp(u);  // 回溯
        }

        /*
       查询区间[l,r]的最大值
         */
        public int query(int u, int lc, int rc, int l, int r) {
            if (lc >= l && rc <= r) return tr[u].max;
            lazyCreate(u);  // 冬天开点
            pushDown(u);    // 下传懒标记
            int mid = lc + (rc - lc) / 2, res = 0;
            if (l <= mid) res = query(tr[u].ls, lc, mid, l, r);
            if (r > mid) res = Math.max(res, query(tr[u].rs, mid + 1, rc, l, r));   // 记得取左右子节点的最大值
            return res; // 返回最大值
        }

        /*
        按需动态开点
         */
        public void lazyCreate(int u) {
            if (tr[u].ls == 0) {    // 左子节点不存在 -> 创建并构建连接
                tr[u].ls = cnt++;
                tr[tr[u].ls] = new Node();
            }
            if (tr[u].rs == 0) {
                tr[u].rs = cnt++;
                tr[tr[u].rs] = new Node();
            }
        }

        /*
        下传懒标记
         */
        public void pushDown(int u) {
            int v = tr[u].add;  // 节点u下传下来的懒标记
            if (v != 0) {   // 当且仅当懒标记不为0才进行下传
                // 下传懒标记至子节点(累计)
                tr[tr[u].ls].add += v;
                tr[tr[u].rs].add += v;
                // 更新左右子节点的值(累计)
                tr[tr[u].ls].max += v;
                tr[tr[u].rs].max += v;
                tr[u].add = 0;  // 下传懒标记完成撤销u的懒标记
            }
        }

        /*
        回溯更新u的最大值
         */
        public void pushUp(int u) {
            tr[u].max = Math.max(tr[tr[u].ls].max, tr[tr[u].rs].max);
        }

        public boolean book(int start, int end) {
            // 最大值>=2说明区间[start,end-1]存在某个点覆盖了2次
            if (query(0, 0, N, start, end - 1) >= 2) return false;
            update(0, 0, N, start, end - 1, 1);
            return true;
        }
    }
}

做完这两题估计对线段树有了充分了解了！

3.差分数组->「区间修改 & 单点查询」：

差分区间求和:将每个区间覆盖信息转化为变化量记录,最后从头开始统计变化量就可以将总的变化量求出来

比喻成公交车:上车就表示该时刻t1->新区间加入乘客+1；下车就表示区间结束->下一个时刻(t2+1)乘客-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        //  注意航班编号为1-n
        // 变化量计数器:索引[0,n-1]
        int[] counter = new int[n];
        // 遍历每个区间
        for (int[] booking : bookings) {
            // 因为航班编号为1-n,因此左偏移一位才是counter索引
            counter[booking[0] - 1] += booking[2];
            // 这里原本有+1又向左偏移一位就是原本的,要判断区间是否合法
            if(booking[1] < n) counter[booking[1]] -= booking[2];
        }
        // 该站人数=上一站人数+该站变化量
        // 注意最初的一站就是0+counter[0]=counter[0]
        for (int i = 1; i < n; i++) {
            counter[i] += counter[i - 1];
        }
        return counter;
    }
}