圣诞节学算法---线段树

news/2024/10/31 1:31:51/

线段树

快到圣诞节了,圣诞树是不是很漂亮?今天我们就来学习一下它的近亲的线段树
(话说这两玩意好像除了读音相似没啥关系)

引入

例题 1

给定一个数组 aaa 求数组中下标为l−rl - rlr元素的和

看到这题大家都很容易想到用前缀和以O(n)O(n)O(n)预处理,O(1)O(1)O(1)求解

例题 2

给定一个数组 aaa ,操作次数 ,及操作符optoptopt
opt=1opt=1opt=1时 求数组中下标为l−rl - rlr元素的和,
opt=2opt=2opt=2时 将数组中下标为l−rl - rlr元素的+ddd

很明显如果我们用前缀和优化,虽然查询很快,但每次修改都是O(r−l+1)O(r-l+1)O(rl+1),当操作次数多时,仍会超时

么有没有一种查询快且修改快的东西呢?
那就是——线段树

线段树概念

“线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。”(选自百度)

有了线段树,我们就可以在O(logn)O(log n)O(logn)的时间内进行修改和查询

模板

现附上大家最爱的模板

struct SegmentTree{int l,r,size;ll sum,tag;#define ls(x) (x<<1)#define rs(x) (x<<1|1)
}tr[MAX*4];ll a[MAX];inline void Push_up(int rt){tr[rt].sum = tr[ls(rt)].sum+tr[rs(rt)].sum;
}void Build(int l,int r,int rt){tr[rt].l = l; tr[rt].r = r; tr[rt].size = r-l+1;if(l == r){tr[rt].sum = a[l];return;}int mid = (l+r)>>1;Build(l,mid,ls(rt));Build(mid+1,r,rs(rt));Push_up(rt);
}inline void Push_down(int rt){if(!tr[rt].tag) return;tr[ls(rt)].tag += tr[rt].tag;tr[rs(rt)].tag += tr[rt].tag;tr[ls(rt)].sum += tr[rt].tag*tr[ls(rt)].size;tr[rs(rt)].sum += tr[rt].tag*tr[rs(rt)].size;tr[rt].tag = 0;
}void Update(int rt,int l,int r,ll c){if(tr[rt].l >= l && tr[rt].r <= r){tr[rt].sum += tr[rt].size*c;tr[rt].tag += c;return;}Push_down(rt);int mid = (tr[rt].l+tr[rt].r)>>1;if(mid >= l) Update(ls(rt),l,r,c);if(mid <  r) Update(rs(rt),l,r,c);Push_up(rt);
}ll Query(int rt,int l,int r){if(tr[rt].l >= l && tr[rt].r <= r) return tr[rt].sum;Push_down(rt);int mid = (tr[rt].l+tr[rt].r)>>1;ll cnt = 0;if(mid >= l) cnt += Query(ls(rt),l,r);if(mid <  r) cnt += Query(rs(rt),l,r);return cnt;
}

线段树构造

线段树
图片来源于网络

线段树的构造如其概念所示,采用二分思想,每个节点贮存范围与范围权值和,其左右子树范围分别为父节点的范围的左半段与右半段,直到范围内只剩一个元素

由于它是完全二叉树,所以我们可以用下标的2倍储存其左节点,二倍加一储存右节点

代码实现

注: rt<<1=rt∗2,,rt<<1∣1=rt∗2+1rt<<1 = rt * 2,,rt<<1|1 = rt * 2+1rt<<1=rt2,rt<<1∣1=rt2+1

inline void Push_up(int rt){//将左右子树求和sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void Build(int l,int r,int rt){//l表示左边界,rb表示右边界,rt表示目前位置 if(l == r){sum[rt] = a[l];return;}int mid = (l+r)>>1;Build(l,mid,rt<<1);//左子树Build(mid+1,r,rt<<1|1);//右子数Push_up(rt);//求和
}

线段树区间查询

线段树区间查询
图片来源于网络

如图所示,线段树的查询就是不断向下找,直到节点范围在查询范围内即可

代码实现

long long Query(int nl,int nr,int l,int r,int rt){
//nl,nr为要查询的左右边界,l,r为目前查询到的左右边界.rt为目前位置if(l >= nl && r <= nr) return sum[rt];//如果整个在查询范围内,就不用查下去了int mid = (l+r)>>1;int ans = 0;//存和if(mid >= nl) ans += Query(nl,nr,l,mid,rt<<1);//查左子树if(mid < nr) ans += Query(nl,nr,mid+1,r,rt<<1|1);//查右子树return ans;
}

区间修改&懒标记

懒标记是线段树的核心

修改区间[l,r],[l,r]需要进行打懒标记的操作来减少时间消耗。
毕竟如果你不查询到这个节点这个节点也没必要一直改呀

设一个数组 tag , tag[i] 表示编号为 i 的节点的懒标记。

代码实现(以区间求和为例)

inline void Push_down(long long rt,long long l,long long r){if(!tag[rt]) return;long long mid = (l+r)>>1;tag[rt<<1] += tag[rt];tag[rt<<1|1] += tag[rt];//将懒标记传到儿子树sum[rt<<1] += (mid-l+1)*tag[rt];sum[rt<<1|1] += (r-mid)*tag[rt];//懒标记对儿子树进行修改tag[rt] = 0;
}
void Update(long long nl,long long nr,long long c,long long l,long long r,long long rt){
//c表示要加的数,其余同上if(l >= nl && r <= nr){sum[rt] += c*(r-l+1);tag[rt] += c;return;}int mid = (l+r)>>1;Push_down(rt,l,r);if(mid >= nl) Update(nl,nr,c,l,mid,rt<<1);if(mid < nr) Update(nl,nr,c,mid+1,r,rt<<1|1);Push_up(rt);//修改完再求和
}

至此,线段树基本就讲完了,是不是非常简单

当然线段树不只是用来求和,在其他区间问题也有广泛应用

例题 — [TJOI2018]数学计算

题目描述

小豆现在有一个数 xxx,初始值为 111。小豆有 QQQ 次操作,操作有两种类型:

1 m:将 xxx 变为 x×mx \times mx×m,并输出 xmodMx \bmod MxmodM

2 pos:将 xxx 变为 xxx 除以第 pospospos 次操作所乘的数(保证第 pospospos 次操作一定为类型 1,对于每一个类型 1 的操作至多会被除一次),并输出 xmodMx \bmod MxmodM

输入格式

一共有 ttt 组输入。

对于每一组输入,第一行是两个数字 Q,MQ,MQ,M

接下来 QQQ 行,每一行为操作类型 opopop,操作编号或所乘的数字 mmm(保证所有的输入都是合法的)。

输出格式

对于每一个操作,输出一行,包含操作执行后的 xmodMx \bmod MxmodM 的值。

样例 #1

样例输入 #1
1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7
样例输出 #1
2
1
2
20
10
1
6
42
504
84

提示

对于 20%20\%20% 的数据,1≤Q≤5001 \le Q \le 5001Q500

对于 100%100\%100% 的数据,1≤Q≤1051 \le Q \le 10^51Q105t≤5,M≤109t \le 5, M \le 10^9t5,M1090<m≤1090 < m \leq 10^90<m109

线段树维护,树顶为答案

#include<bits/stdc++.h>
#define ll long long
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define lson l,mid,ls
#define rson mid+1,r,rs
using namespace std;
const int MAX = 1e5+10;
int T;
ll Q,M;
ll tree[MAX<<2];
inline void Push_up(int rt){tree[rt] = tree[ls]*tree[rs]%M;
}
void Build(int l,int r,int rt){if(l == r){tree[rt] = 1;return;}tree[rt] = 1;Build(lson);Build(rson);
}
void Update(int l,int r,int rt,int pos,int val){if(l == r){tree[rt] = (val == 0) ? 1 : val;return;}if(mid >= pos) Update(lson,pos,val);else Update(rson,pos,val);Push_up(rt);
}
int main(){ios::sync_with_stdio(false);cin >> T;while(T--){cin >> Q >>M;Build(1,Q,1);for(int pos = 1;pos <= Q;pos++){int op,m;cin >> op >> m;if(op == 1){Update(1,Q,1,pos,m);cout << tree[1]%M << "\n";}else{Update(1,Q,1,m,0);cout << tree[1]%M << "\n";}}}return 0;
}

总结

线段树,是一种维护区间和的树形结构,能在O(logn)O(logn)O(logn)进行区间修改以及查询
以上就是基本的线段树,如果有不懂的欢迎评论区讨论


http://www.ppmy.cn/news/6045.html

相关文章

聊聊首次使用航顺HK32F030C8T6的体验

先说结论&#xff0c;项目基本上开发测试完成了,mcu运行正常。 这个项目是一个智能家居的项目&#xff0c;主板和副板都使用了HK32F030C8T6&#xff0c;这也是笔者第一次使用航顺的芯片。 关于这个芯片的资料&#xff0c;从官网只能下载到datasheet和user mannal的pdf文档&am…

IO多路复用实现方式

IO分类 NIO NIO即同步非阻塞IO。非阻塞的recvfrom系统调用之后&#xff0c;进程并没有被阻塞&#xff0c;内核马上返回进程&#xff0c;如果数据还没准备好&#xff0c;此时会返回一个error。进程在返回之后&#xff0c;可以干点别的事情&#xff0c;然后再发起recvfrom系统调…

硬盘 / 硬盘控制器主要端口寄存器 / Controller Register

文章目录IDE 与 SATA硬盘分区表结构硬盘控制器主要端口寄存器data 寄存器Error && FeaturesErrorFeaturesSector countLBA low | mid | highdevice 寄存器StatusCommandIDE 与 SATA 很久以前&#xff0c;硬盘控制器和硬盘是分开的&#xff0c;后面开发了一个新接口&am…

【小程序】案例 - 本地生活(首页)

1. 首页效果以及实现步骤 新建项目并梳理项目结构 配置导航栏效果 配置 tabBar 效果 实现轮播图效果 实现九宫格效果 实现图片布局 2. 接口地址 获取轮播图数据列表的接口 【GET】 https://www.escook.cn/slides 获取九宫格数据列表的接口 【GET】 https://www.esco…

C++内存管理

内存管理 c&#xff1a;malloc、calloc、realloc、free c&#xff1a;new&#xff08;不会初始化&#xff09;、delete 内存管理方式 对于内置类型 //申请和释放单个元素的空间&#xff0c;使用new和delete操作符 int* p1 new int;//申请1个int类型的空间 delete p1;int*…

jenkins pipeline 指定执行节点

第一种写法&#xff1a; pipeline { agent { label “slave-hw” } stages { stage(‘执行更新程序包’) { steps { sh ‘cd /apps/nedy/nedy/csctbb/HWCLOUD ; sh test.sh’ } } stage(‘是否继续’) { steps { input message: ‘确认继续吗&#xff1f;’, ok: ‘确认’ } } …

【PAT甲级 - C++题解】1113 Integer Set Partition

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 &#x1f4da;专栏地址&#xff1a;PAT题解集合 &#x1f4dd;原题地址&#xff1a;题目详情 - 1113 Integer Set Partition (pintia.cn) &#x1f511;中文翻译&#xff1a;整数集合划分 &…

四、网络层(七)网络层设备

目录 7.1 路由器的组成和功能 7.2 路由表与路由转发 7.1 路由器的组成和功能 路由器是一种具有多个输入/输出端口的专用计算机&#xff0c;其任务是连接不同的网络&#xff08;可以是异构的&#xff09;并完成路由转发。在多个逻辑网络&#xff08;即多个广播域&#xff…