当前位置：网站首页>线段树以及使用
线段树以及使用
2022-06-29 06:41:00 【今天也要写bug、】
文章目录
线段树的概念
线段树能把一些对于区间（或者线段）的修改、维护，从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;
};
修改某一段区间
以加法为例，如果我们要对某一段区间的所有数都加上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);
}
区间更新
区间更新的意思是将一段区间的所有值都修改成某个值。
为此需要一个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);//更新父亲节点的累加和
}
区间查询
如果查询的区间被非叶子节点的区间覆盖，则直接返回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;
}
总代码
#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;
};
线段树的使用场景
线段树的使用场景为：根节点左子树可以得到一个信息，右子树也可以得到一个信息，根节点的信息可以由左右两边的信息在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;
}
};
使用线段树的解法：
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;
}
};
值得注意的是，为了能够少开空间和提高速度，我们也可以不用数组的方式，而是采用二叉树的形式：
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;
}
};
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++);
}
}
}
};
线段树解法：
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;
}
};
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);
}
};
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();
}
};
不过由于这个题是求区间和，当然用线段树来做也可以：
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);
}
};
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;
}
};
边栏推荐
- ROS2中的行为树 BehaviorTree
- How to share the virtual environment of pycharm to jupyter Lab
- Common MySQL errors and solutions summarized painstakingly (II)
- [industrial control old horse] detailed design of PLC six way responder system
- 反思 - 中小公司项目管理思维 - 先将产品做出来，先将功能做出来
- js异或混淆代码
- DataTables screen error Popup
- Protobuf 二进制文件学习及解析
- AI and the meta universe sparked a spark: human beings lost only shackles and gained all-round liberation
- SQL injection bypass (6)
猜你喜欢
![[industrial control old horse] detailed explanation of the design scheme of the running lamp control system based on Siemens S7-200PLC](/img/c5/9383a02050c83b26bb56f4045b0774.png)
[industrial control old horse] detailed explanation of the design scheme of the running lamp control system based on Siemens S7-200PLC
【深度之眼吴恩达机器学习作业班第四期】Linear Regression with One Variable,单变量线性回归
Protobuf 二进制文件学习及解析
Appium 环境搭建
Schnuka: 3D visual inspection scheme 3D visual inspection application industry
Roblox剑九之剑二
Vibration signal generation and processing based on MATLAB Doppler effect
Common MySQL errors and solutions summarized painstakingly (I)
How to permanently set Mysql to utf8 encoding?
电检码配置
随机推荐
ROS2中的行为树 BehaviorTree
面试官：为什么数据库连接很消耗资源，资源都消耗在哪里？
Cross domain data request using jsonp
【深度之眼吴恩达第四期作业班】多元线性回归Linear Regression with multiple variables总结
Select distinct on statement in kingbasees
Vulnhub's dc7 target
ROS当中的仿真时间以及Bag包操作
Alicloud access resource: nosuchkey
SQL SERVER 2008 发布订阅到SQL Server 2017避坑指南
【量化投资系统】因子处理安装talib
How to solve the cross domain problem of mobile phone accessing the web in the web development scenario
低配MySQL数据库几十秒插入百万数据
声波通讯 - 流式数据处理 - 窗口对齐
SVM，人脸识别遇到的问题及解决方法
ShapeShifter: Robust Physical Adversarial Attack on Faster R-CNN Object Detector
Gateway controller communication protocol
Protobuf 二进制文件学习及解析
Viewing application and installation of Hana database license
Using cdockablepane to realize floating window in MFC
电检码配置