-
线段树以及使用
线段树的概念
线段树能把一些对于区间（或者线段）的修改、维护，从O(N)的时间复杂度变成O（logN）。
线段树是一种二叉树，也就是对于一段数组，如果用一个二叉树来表示。[L,R]区间会被划分为两个区间分别是[L,(L+R)/2]和[(L+R)/2+1,R]这两个小区间。然后再递归下去分直到L=R。
比如说一个长度为4的数组，我们可以表示成这样：
如果我们想求
1~3区间的和，那么只需要得到1~2区间的和与3就可以了，这比直接for循环遍历要快很多。表示一段长度为5的数组：
但是我们不用二叉树的形式来表示这个树，而是用数组（数组为0的下标不用）的形式表示，对于一个节点，如果它的下标为i，那么其左孩子下标为
2*i，右孩子下标为2*i+1,它的父节点下标为i/2而对于线段树数组的大小，从上面的两个图不难看出来，对于区间中数的个数n：
- 如果n=2k，需要2n个节点。
- 如果n=2^i+1，此时情况最坏需要4n个节点（估计值）。
线段树的代码
线段树的构建
#include<iostream> #include<vector> using namespace std; class SegmentTree { public: SegmentTree(const vector<int>& origin) { MAXN = origin.size() + 1; arr.resize(MAXN); for (int i = 1; i < MAXN; i++) { arr[i] = origin[i - 1]; } //左移两位，相当于*4, sum.resize(MAXN << 2); lazy.resize(MAXN << 2); change.resize(MAXN << 2); update.resize(MAXN << 2); } //build运用递归来计算线段树的区间和 //l与r代表arr的范围，rt代表该范围的和要填到sum数组的哪个下标上 void build(int l, int r, int rt) { //l==r时，说明为叶子节点，比如1~1，2~2 if (l == r) { sum[rt] = arr[l]; return; } //求l到r的和，将l到r的部分分为两段 //分别递归求出这两段的值，然后调用pushUp即可求出l到r的值 //使用位运算完成，比直接乘速度会快一些 int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, (rt << 1) | 1); pushUp(rt);//计算向上返回累加和 }; //pushUp用来计算l~r左右区间的和 void pushUp(int rt) { sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1]; } private: //要开辟数组的大小，也就是4n int MAXN; //arr维护的是原序列信息从0开始，但是在这里arr从1开始 vector<int>arr; //线段树维护的区间和 vector<int>sum; //为累加懒惰信息标记 vector<int>lazy; //对应位置的更新值 vector<int>change; //为更新懒惰标记 vector<bool>update; };- 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
修改某一段区间
以加法为例，如果我们要对某一段区间的所有数都加上C，我们如果直接修改sum数组的叶子节点（叶子节点就是每个数），会非常慢。此时采用懒更新的策略。
把加C的操作直接更新到非叶子节点，用lazy数组保存加的C。
比如我们对
1~10这段范围的每个数都加上2，那么我们直接对保存1~10区间的非叶子节点加上20，而不是给1~10每个叶子都加上2，lazy数组记录+2的操作。//pushUp用来计算l~r左右区间的和 void pushUp(int rt) { sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1]; } //rt表示父节点的下标，ln和rn表示该父节点左右孩子有几个数 void pushDown(int rt, int ln, int rn) { //update在前，因为update会将lazy数组清空 //如果lazy数组不为0，说明update操作先于lazy操作 if (update[rt]) { update[rt << 1] = true;//往下发 update[rt << 1 | 1] = true; change[rt << 1] = change[rt]; change[rt << 1 | 1] = change[rt]; lazy[rt << 1] = 0;//清空左右孩子的懒数组 lazy[rt << 1 | 1] = 0; sum[rt << 1] = change[rt] * ln;//左孩子总和 sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和 update[rt] = false;//当前位置已经下发改成false; } if (lazy[rt]!=0) { //将根节点的懒信息下发给左右孩子 lazy[rt << 1] += lazy[rt]; lazy[(rt << 1) | 1] += lazy[rt]; sum[rt << 1] += lazy[rt] * ln; sum[rt << 1 | 1] += lazy[rt] * rn; //父节点的懒信息置0 lazy[rt] = 0; } } //L和R表示实际要修改的范围，给这一段范围每个数都加上C //l到r表示当前来到的范围，rt 表示这个范围所在sum与lazy数组的下标 void add(int L, int R, int C, int l, int r, int rt) { //如果当前来到的范围，在L和R的范围，我们就懒更新 if (L <= l && r <= R) { //修改相关信息 sum[rt] += C * (r - l + 1); //lazy表示懒的值 lazy[rt] += C; return; } //当前任务躲不掉，无法懒更新，要往下发 //比如对3~7范围+2 //但是l和r的范围是2~5，很明显2没法懒更新 int mid = (l + r) >> 1; //之前的老任务可能存在懒信息，比如对3~7范围+2之前，已经对2~5范围加3了 //因此先将懒信息下发给左右孩子 pushDown(rt, mid - l + 1, r - mid); //之前的老任务更新完，开始更新新任务 if (L <= mid) {//左孩子需要下发任务 add(L, R, C, l, mid, rt << 1); } if (R > mid) {//右孩子需要下发任务 add(L, R, C, mid + 1, r, rt << 1 | 1); } //更新父亲的累加和 pushUp(rt); }- 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
区间更新
区间更新的意思是将一段区间的所有值都修改成某个值。
为此需要一个bool类型的标记数组update来表示是否对线段树的某个节点进行修改。
用change数组表示已经修改成了哪个值。并且lazy数组清空。//pushUp用来计算l~r左右区间的和 void pushUp(int rt) { sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1]; } //rt表示父节点的下标，ln和rn表示该父节点左右孩子有几个数 void pushDown(int rt, int ln, int rn) { //update在前，因为update会将lazy数组清空 //如果lazy数组不为0，说明update操作先于lazy操作 if (update[rt]) { update[rt << 1] = true;//往下发 update[rt << 1 | 1] = true; change[rt << 1] = change[rt]; change[rt << 1 | 1] = change[rt]; lazy[rt << 1] = 0;//清空左右孩子的懒数组 lazy[rt << 1 | 1] = 0; sum[rt << 1] = change[rt] * ln;//左孩子总和 sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和 update[rt] = false;//当前位置已经下发改成false; } if (lazy[rt]!=0) { //将根节点的懒信息下发给左右孩子 lazy[rt << 1] += lazy[rt]; lazy[(rt << 1) | 1] += lazy[rt]; sum[rt << 1] += lazy[rt] * ln; sum[rt << 1 | 1] += lazy[rt] * rn; //父节点的懒信息置0 lazy[rt] = 0; } } //L和R表示实际要修改的范围，给这一段范围每个数都改为C //l到r表示当前来到的范围，rt 表示这个范围所在sum与lazy、change数组的下标 void upDate(int L, int R, int C, int l, int r, int rt) { if (L <= l && r <= R) { update[rt] = true;//标记已经更新过 change[rt] = C; sum[rt] = C * (r - l + 1); lazy[rt] = 0;//清空 return; } //当前任务躲不掉，无法懒更新，要往下发 int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid); if (L <= mid) { upDate(L, R, C, l, mid, rt << 1); } if (R > mid) { upDate(L, R, C, mid + 1, r, rt << 1 | 1); } pushUp(rt);//更新父亲节点的累加和 }- 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
区间查询
如果查询的区间被非叶子节点的区间覆盖，则直接返回sum数组里面的值即可。
如果没有完全覆盖则先将懒标记往左右子树传。//查询L~R区间的累加和，当前的区间为l~r，对应的数组下标为rt long long query(int L, int R, int l, int r, int rt) { //刚好覆盖这个区间直接在这里面拿值 if (L <= l && r <= R) { return sum[rt]; } int mid = (l + r) >> 1; //先将懒信息分配给左右孩子 pushDown(rt, mid - l + 1, r - mid); long long ans = 0; //到左右子树的区间查询 if (L <= mid) { ans += query(L, R, l, mid, rt << 1); } if (R > mid) { ans += query(L, R, mid + 1, r, rt << 1 | 1); } return ans; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
总代码
#pragma once #pragma once #include<iostream> #include<vector> using namespace std; class SegmentTree { public: SegmentTree(const vector<int>& origin) { MAXN = origin.size() + 1; arr.resize(MAXN); for (int i = 1; i < MAXN; i++) { arr[i] = origin[i - 1]; } //左移两位，相当于*4, sum.resize(MAXN << 2); lazy.resize(MAXN << 2); change.resize(MAXN << 2); update.resize(MAXN << 2); } //build运用递归来计算线段树的区间和 //l与r代表arr的范围，rt代表该范围的和要填到sum数组的哪个下标上 void build(int l, int r, int rt) { //l==r时，说明为叶子节点，比如1~1，2~2 if (l == r) { sum[rt] = arr[l]; return; } //求l到r的和，将l到r的部分分为两段 //分别递归求出这两段的值，然后调用pushUp即可求出l到r的值 //使用位运算完成，比直接乘速度会快一些 int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, (rt << 1) | 1); pushUp(rt);//计算向上返回累加和 }; //pushUp用来计算l~r左右区间的和 void pushUp(int rt) { sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1]; } //rt表示父节点的下标，ln和rn表示该父节点左右孩子有几个数 void pushDown(int rt, int ln, int rn) { //update在前，因为update会将lazy数组清空 //如果lazy数组不为0，说明update操作先于lazy操作 if (update[rt]) { update[rt << 1] = true;//往下发 update[rt << 1 | 1] = true; change[rt << 1] = change[rt]; change[rt << 1 | 1] = change[rt]; lazy[rt << 1] = 0;//清空左右孩子的懒数组 lazy[rt << 1 | 1] = 0; sum[rt << 1] = change[rt] * ln;//左孩子总和 sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和 update[rt] = false;//当前位置已经下发改成false; } if (lazy[rt]!=0) { //将根节点的懒信息下发给左右孩子 lazy[rt << 1] += lazy[rt]; lazy[(rt << 1) | 1] += lazy[rt]; sum[rt << 1] += lazy[rt] * ln; sum[rt << 1 | 1] += lazy[rt] * rn; //父节点的懒信息置0 lazy[rt] = 0; } } //L和R表示实际要修改的范围，给这一段范围每个数都加上C //l到r表示当前来到的范围，rt 表示这个范围所在sum与lazy数组的下标 void add(int L, int R, int C, int l, int r, int rt) { //如果当前来到的范围，在L和R的范围，我们就懒更新 if (L <= l && r <= R) { //修改相关信息 sum[rt] += C * (r - l + 1); //lazy表示懒的值 lazy[rt] += C; return; } //当前任务躲不掉，无法懒更新，要往下发 //比如对3~7范围+2 //但是l和r的范围是2~5，很明显2没法懒更新 int mid = (l + r) >> 1; //之前的老任务可能存在懒信息，比如对3~7范围+2之前，已经对2~5范围加3了 //因此先将懒信息下发给左右孩子 pushDown(rt, mid - l + 1, r - mid); //之前的老任务更新完，开始更新新任务 if (L <= mid) {//左孩子需要下发任务 add(L, R, C, l, mid, rt << 1); } if (R > mid) {//右孩子需要下发任务 add(L, R, C, mid + 1, r, rt << 1 | 1); } //更新父亲的累加和 pushUp(rt); } //L和R表示实际要修改的范围，给这一段范围每个数都改为C //l到r表示当前来到的范围，rt 表示这个范围所在sum与lazy、change数组的下标 void upDate(int L, int R, int C, int l, int r, int rt) { if (L <= l && r <= R) { update[rt] = true;//标记已经更新过 change[rt] = C; sum[rt] = C * (r - l + 1); lazy[rt] = 0;//清空 return; } //当前任务躲不掉，无法懒更新，要往下发 int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid); if (L <= mid) { upDate(L, R, C, l, mid, rt << 1); } if (R > mid) { upDate(L, R, C, mid + 1, r, rt << 1 | 1); } pushUp(rt);//更新父亲节点的累加和 } //查询L~R区间的累加和，当前的区间为l~r，对应的数组下标为rt long long query(int L, int R, int l, int r, int rt) { //刚好覆盖这个区间直接在这里面拿值 if (L <= l && r <= R) { return sum[rt]; } int mid = (l + r) >> 1; //先将懒信息分配给左右孩子 pushDown(rt, mid - l + 1, r - mid); long long ans = 0; //到左右子树的区间查询 if (L <= mid) { ans += query(L, R, l, mid, rt << 1); } if (R > mid) { ans += query(L, R, mid + 1, r, rt << 1 | 1); } return ans; } private: //要开辟数组的大小，也就是4n int MAXN; //arr维护的是原序列信息从0开始，但是在这里arr从1开始 vector<int>arr; //线段树维护的区间和 vector<int>sum; //为累加懒惰信息标记 vector<int>lazy; //对应位置的更新值 vector<int>change; //为更新懒惰标记 vector<bool>update; };- 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
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
线段树的使用场景
线段树的使用场景为：根节点左子树可以得到一个信息，右子树也可以得到一个信息，根节点的信息可以由左右两边的信息在O（1）的范围内得到。比如区间查询、增加、相乘。
699. 掉落的方块
699. 掉落的方块
这道题是一个区间更新的题，当一个方块落到一个区间以后，我们需要查询该区间原来的最大值，然后加上这个方块的高度，最后更新最大值。不用线段树的解法：
class Solution { public: vector<int> fallingSquares(vector<vector<int>>& positions) { int n=positions.size(); vector<int>res(n); for(int i=0;i<n;i++) { int left=positions[i][0]; int high=positions[i][1]; int right=left+high-1; res[i]+=high; for(int j=0;j<i;j++) { int beforeLeft=positions[j][0]; int beforeHigh=positions[j][1]; int beforeRight=beforeLeft+beforeHigh-1; //在落线第i个之前，看一下i前面那几个有没有在i下面的，如果有就叠加 if (right >= beforeLeft && beforeRight >= left) { res[i] = max(res[i], res[j] + positions[i][1]); } } } //第k个方块落下后，有可能并没有增加高度，因此结果还是前一个 for(int k=1;k<n;k++) { res[k]=max(res[k],res[k-1]); } return res; } };- 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
使用线段树的解法：
class Solution { public: void segmentTree(int size) { MAXN = size; maxHigh.resize(MAXN<<2); change.resize(MAXN<<2); update.resize(MAXN<<2); } //pushUp用来计算l~r左右区间的和 void pushUp(int rt) { maxHigh[rt] = max(maxHigh[rt << 1],maxHigh[(rt << 1) | 1]); } void pushDown(int rt) { if (update[rt]) { update[rt << 1] = true;//往下发 update[rt << 1 | 1] = true; change[rt << 1] = change[rt]; change[rt << 1 | 1] = change[rt]; maxHigh[rt<<1]=change[rt]; maxHigh[rt<<1|1]=change[rt]; update[rt] = false;//当前位置已经下发改成false; } } void upDate(int L, int R, int C, int l, int r, int rt) { if (L <= l && r <= R) { update[rt] = true;//标记已经更新过 change[rt]=C; maxHigh[rt]=C; return; } //当前任务躲不掉，无法懒更新，要往下发 int mid = (l + r) >> 1; pushDown(rt); if (L <= mid) { upDate(L, R, C, l, mid, rt << 1); } if (R > mid) { upDate(L, R, C, mid + 1, r, rt << 1 | 1); } pushUp(rt);//更新父亲节点的累加和 } //查询L~R区间的累加和，当前的区间为l~r，对应的数组下标为rt int query(int L, int R, int l, int r, int rt) { //刚好覆盖这个区间直接在这里面拿值 if (L <= l && r <= R) { return maxHigh[rt]; } int mid = (l + r) >> 1; //先将懒信息分配给左右孩子 pushDown(rt); int left=0; int right=0; //到左右子树的区间查询 if (L <= mid) { left+= query(L, R, l, mid, rt << 1); } if (R > mid) { right= query(L, R, mid + 1, r, rt << 1 | 1); } return max(left,right); } int MAXN; vector<int>maxHigh; vector<int>change; vector<bool>update; public: vector<int> fallingSquares(vector<vector<int>>& positions) { int size=0; for(auto& position : positions) { size=max(size,position[0]+position[1]); } segmentTree(size); vector<int>ans; for (auto& position : positions) { int x = position[0], h = position[1]; int oldHigh=query(x,x+h-1,0,MAXN,1); upDate(x, x + h - 1, oldHigh+h, 0,MAXN,1); ans.push_back(maxHigh[1]); } return ans; } };- 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
值得注意的是，为了能够少开空间和提高速度，我们也可以不用数组的方式，而是采用二叉树的形式：
class Solution { public: class Node { public: Node():val(0), add(0),left(nullptr), right(nullptr){} // 左右孩子节点 Node* left,*right; // 当前节点值，以及懒惰标记的值 int val,add; }; int N = (int) 1e9; Node* root = new Node(); void update(Node*& node, int start, int end, int l, int r, int val) { if (l <= start && end <= r) { node->val = val; node->add = val; return ; } pushDown(node); int mid = (start + end) >> 1; if (l <= mid) update(node->left, start, mid, l, r, val); if (r > mid) update(node->right, mid + 1, end, l, r, val); pushUp(node); } int query(Node*& node, int start, int end, int l, int r) { if (l <= start && end <= r) return node->val; pushDown(node); int mid = (start + end) >> 1, ans = 0; if (l <= mid) ans = query(node->left, start, mid, l, r); if (r > mid) ans = max(ans, query(node->right, mid + 1, end, l, r)); return ans; } void pushUp(Node*& node) { // 每个节点存的是当前区间的最大值 node->val = max(node->left->val, node->right->val); } void pushDown(Node*& node) { if (node->left == nullptr) node->left = new Node(); if (node->right == nullptr) node->right = new Node(); if (node->add == 0) return ; node->left->val = node->add; node->right->val = node->add; node->left->add = node->add; node->right->add = node->add; node->add = 0; } public: vector<int> fallingSquares(vector<vector<int>>& positions) { vector<int>ans(positions.size()); int i=0; for (auto& position : positions) { int x = position[0], h = position[1]; int oldHigh=query(root,0,N,x,x+h-1); update(root,0,N,x,x + h - 1, oldHigh+h); ans[i]=root->val; i++; } return ans; } };- 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
715. Range 模块
715. Range 模块
一般解法：class RangeModule { map<int, int> m; public: RangeModule() { } void addRange(int left, int right) { auto it = m.lower_bound(left); for (auto i = it; i != m.end() && i->second < right;) { int l = i -> second, r = i -> first; if (l < left) left = l; if (r > right) right = r; m.erase(i++); } m[right] = left; } bool queryRange(int left, int right) { auto it = m.lower_bound(right); if (it == m.end() || it -> second >= right) return false; int l = it -> second; while (l > left) { if (m.count(l)) { l = m[l]; } else { return false; } } return true; } void removeRange(int left, int right) { // 右端点应该大于当前节点左端点才有交集，等于时没有交集 auto it = m.upper_bound(left); for (auto i = it; i != m.end() && i->second < right;) { int l = i -> second, r = i -> first; if (l < left) { m[left] = l; } if (r > right) { m[r] = right; } else { m.erase(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
线段树解法：
class RangeModule { public: RangeModule() { } void addRange(int left, int right) { // 1 表示覆盖；-1 表示取消覆盖 update(root, 1, N, left, right - 1, 1); } bool queryRange(int left, int right) { return query(root, 1, N, left, right - 1); } void removeRange(int left, int right) { // 1 表示覆盖；-1 表示取消覆盖 update(root, 1, N, left, right - 1, -1); } class Node { public: Node():cover(false), add(0),left(nullptr), right(nullptr){} Node* left, *right; //表示当前区间是否被覆盖 bool cover; int add; }; int N = (int) 1e9; Node* root = new Node(); void update(Node*& node, int start, int end, int l, int r, int val) { if (l <= start && end <= r) { // 1 表示覆盖；-1 表示取消覆盖 node->cover = (val == 1); node->add = val; return; } int mid = (start + end) >> 1; pushDown(node, mid - start + 1, end - mid); if (l <= mid) update(node->left, start, mid, l, r, val); if (r > mid) update(node->right, mid + 1, end, l, r, val); pushUp(node); } bool query(Node*& node, int start, int end, int l, int r) { if (l <= start && end <= r) return node->cover; int mid = (start + end) >> 1; pushDown(node, mid - start + 1, end - mid); // 查询左右子树是否被覆盖 bool ans = true; if (l <= mid) ans = ans && query(node->left, start, mid, l, r); if (r > mid) ans = ans && query(node->right, mid + 1, end, l, r); return ans; } void pushUp(Node*& node) { // 向上更新 node->cover = node->left->cover && node->right->cover; } void pushDown(Node*& node, int leftNum, int rightNum) { if (node->left == nullptr) node->left = new Node(); if (node->right == nullptr) node->right = new Node(); if (node->add == 0) return; node->left->cover = node->add == 1; node->right->cover = node->add == 1; node->left->add = node->add; node->right->add = node->add; node->add = 0; } };- 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
307. 区域和检索 - 数组可修改
307. 区域和检索 - 数组可修改
这个题用一般方法会超时，因此采用线段树求解：class NumArray { public: class Node { public: Node():val(0), add(0),left(nullptr), right(nullptr){} // 左右孩子节点 Node* left,*right; // 当前节点值，以及懒惰标记的值 int val,add; }; int N; Node* root = new Node(); void update(Node*& node, int start, int end, int l, int r, int val) { if (l <= start && end <= r) { node->val = val; node->add = val; return ; } pushDown(node); int mid = (start + end) >> 1; if (l <= mid) update(node->left, start, mid, l, r, val); if (r > mid) update(node->right, mid + 1, end, l, r, val); pushUp(node); } int query(Node*& node, int start, int end, int l, int r) { if (l <= start && end <= r) return node->val; pushDown(node); int mid = (start + end) >> 1, ans = 0; if (l <= mid) ans += query(node->left, start, mid, l, r); if (r > mid) ans += query(node->right, mid + 1, end, l, r); return ans; } void pushUp(Node*& node) { node->val = node->left->val+node->right->val; } void pushDown(Node*& node) { if (node->left == nullptr) node->left = new Node(); if (node->right == nullptr) node->right = new Node(); if (node->add == 0) return; node->left->val = node->add; node->right->val = node->add; node->left->add = node->add; node->right->add = node->add; node->add = 0; } NumArray(vector<int>& nums) { N = nums.size() - 1; for (int i = 0; i <= N; i++) { update(root, 0, N, i, i, nums[i]); } } void update(int index, int val) { update(root, 0, N, index, index, val); } int sumRange(int left, int right) { return query(root, 0, N, left, right); } };- 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
933. 最近的请求次数
933. 最近的请求次数
这个题直接用队列来实现就可以：class RecentCounter { public: queue<int> q; RecentCounter() { } int ping(int t) { q.push(t); while(!q.empty()&&q.front() + 3000 < t) q.pop(); return q.size(); } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
不过由于这个题是求区间和，当然用线段树来做也可以：
class RecentCounter { public: class Node { public: Node():val(0), add(0),left(nullptr), right(nullptr){} // 左右孩子节点 Node* left,*right; // 当前节点值，以及懒惰标记的值 int val,add; }; int N=1e9; Node* root = new Node(); void update(Node*& node, int start, int end, int l, int r, int val) { if (l <= start && end <= r) { node->val = val; node->add = val; return ; } pushDown(node); int mid = (start + end) >> 1; if (l <= mid) update(node->left, start, mid, l, r, val); if (r > mid) update(node->right, mid + 1, end, l, r, val); pushUp(node); } int query(Node*& node, int start, int end, int l, int r) { if (l <= start && end <= r) return node->val; pushDown(node); int mid = (start + end) >> 1, ans = 0; if (l <= mid) ans += query(node->left, start, mid, l, r); if (r > mid) ans += query(node->right, mid + 1, end, l, r); return ans; } void pushUp(Node*& node) { node->val = node->left->val+node->right->val; } void pushDown(Node*& node) { if (node->left == nullptr) node->left = new Node(); if (node->right == nullptr) node->right = new Node(); if (node->add == 0) return; node->left->val = node->add; node->right->val = node->add; node->left->add = node->add; node->right->add = node->add; node->add = 0; } RecentCounter() { } int ping(int t) { update(root, 1, N, t, t, 1); return query(root, 1, N, max(0, t - 3000), t); } };- 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
732. 我的日程安排表 III
732. 我的日程安排表 III
这是一个区间和的题型。class MyCalendarThree { public: class Node { public: Node():val(0), add(0),left(nullptr), right(nullptr){} // 左右孩子节点 Node* left,*right; // 当前节点值，以及懒惰标记的值 int val,add; }; int N=1e9; Node* root = new Node(); void add(Node*& node, int start, int end, int l, int r, int val) { if (l <= start && end <= r) { node->val += val; node->add += val; return ; } pushDown(node); int mid = (start + end) >> 1; if (l <= mid) add(node->left, start, mid, l, r, val); if (r > mid) add(node->right, mid + 1, end, l, r, val); pushUp(node); } int query(Node*& node, int start, int end, int l, int r) { if (l <= start && end <= r) return node->val; pushDown(node); int mid = (start + end) >> 1, ans = 0; if (l <= mid) ans += query(node->left, start, mid, l, r); if (r > mid) ans += query(node->right, mid + 1, end, l, r); return ans; } void pushUp(Node*& node) { node->val = max(node->left->val,node->right->val); } void pushDown(Node*& node) { if (node->left == nullptr) node->left = new Node(); if (node->right == nullptr) node->right = new Node(); if (node->add == 0) return; node->left->val += node->add; node->right->val += node->add; node->left->add += node->add; node->right->add += node->add; node->add = 0; } MyCalendarThree() { } int book(int start, int end) { // 只用到了 update add(root, 0, N, start, end - 1, 1); // 最大值即为根节点的值 return root->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
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
-
相关阅读:
【Java集合类面试二十】、请介绍LinkedHashMap的底层原理
Reptile_urllib的基本使用
基于SDN技术构建多平面业务承载网络
ES6笔记————let，箭头函数，剩余参数
DataX数据同步
golang不使用go get连接数据库
转换类的具体使用教程
MPLS VPN跨域 Option C2
git的使用流程及git命令总结
【YOLOv7_0.1】网络结构与源码解析
- 原文地址：https://blog.csdn.net/qq_52670477/article/details/125449147