东莞横沥做网站,电子商务网站建设管理实训报告,外贸尾单t恤,成都网站建设、一、线段树
1.区间问题
线段树是一种在算法竞赛中常用来维护区间的数据结构。它思想非常简单#xff0c;就是借助二叉树的结构进行分治#xff0c;但它的功能却非常强大#xff0c;因此在很多类型的题目中都有它的变种#xff0c;很多题目都需要以线段树为基础进行发展。…一、线段树
1.区间问题
线段树是一种在算法竞赛中常用来维护区间的数据结构。它思想非常简单就是借助二叉树的结构进行分治但它的功能却非常强大因此在很多类型的题目中都有它的变种很多题目都需要以线段树为基础进行发展。
具体来讲线段树可以在 O ( log N ) O(\log N) O(logN) 的时间复杂度内实现单点修改和区间修改以及动态区间查询、求和、求最大、求区间最小值等操作。
2.基本结构
通常我们会将线段树构建成二叉树的样子二叉树的每一个结点都表示一段区间并使用数组来进行简化表示。每一个非叶子结点都有左右两棵子树分别表示区间的左右两部分。现以根节点在数组中的下标为 1 1 1则线段树具有以下的性质。
一个结点若其在数组中的下标为 p o s pos pos则它的左右儿子的下标分别为 2 p o s , 2 p o s 1 2pos,2pos1 2pos,2pos1。一个结点表示的区间为 [ l , r ] [l,r] [l,r]则它的左右儿子的表示的区间分别是 [ l , m i d ] , [ m i d 1 , r ] [l,mid],[mid1,r] [l,mid],[mid1,r]其中 m i d ( l r ) / 2 mid(lr)/2 mid(lr)/2。线段树的空间一般要开到 4 n 4n 4n以防止特殊的越界发生。
例如以结点总数 n 10 n10 n10 为例构造的线段树如下所示 3.线段树的建立
下面以维护区间最小值为例来讲解线段树的基本操作
函数包含三个参数分别表示该结点的下标、左端点、右端点。如果左端点等于右端点则说明已经到叶子结点了它的最小值就是它自己直接对其赋值并返回。如果不是叶子结点那么区间 [ l , r ] [l,r] [l,r] 的最小值就是区间 [ l , m i d ] , [ m i d 1 , r ] [l,mid],[mid1,r] [l,mid],[mid1,r] 的最小值的最小值所以应该递归地先求出子区间的最小值再最后得到当前的最小值。
ll tree[4*maxn],a[maxn];
void build(ll pos,ll l,ll r)
{if(lr){tree[l]a[pos];return;}ll mid(lr)1;build(pos1,l,mid);build(pos1|1,mid1,r);tree[pos]min(tree[pos1],tree[pos1|1]);
}建树的时间复杂度为 O ( n ) O(n) O(n)。
4.单点更新
如果这个时候某一个结点的值被更新了那么可以考虑这个结点影响了哪些结点如此只需要在 O ( log n ) O(\log n) O(logn) 的时间就可以完成整棵树的更新了而不需要花费 O ( n ) O(n) O(n) 的时间去重新建树。
思路很简单我们已知被更新结点的下标所以只需要判断它在左边还是右边即可这样每次只选择一边时间复杂度大大降低。但一定要记住这里的更新和建树一样是自下而上更新的所以结点的值应该在递归的时候更新。
void update(ll pos,ll l,ll r,ll x,ll num)
{if(lr){tree[pos]num;return;}ll mid(lr)1;if(xmid)update(pos1,l,mid,x,num);elseupdate(pos1|1,mid1,r,x,num);tree[pos]min(tree[pos1],tree[pos1|1]);
}5.单点查询
和单点更新几乎一致
void query(ll pos,ll l,ll r,ll x)
{if(lr)return tree[pos];ll mid(lr)1;if(xmid)return query(pos1,l,mid,x);elsereturn query(pos1|1,mid1,r,x);
}6.区间查询
因为线段树上的区间划分是固定的很多时候查询不可能刚好是某一个结点所以我们需要对区间进行分段最后依靠递归得到答案。
设我们要查询的区间为 [ s , e ] [s,e] [s,e]则到一个结点时可能有三种情况
若该结点是 [ s , e ] [s,e] [s,e] 的子区间那么直接返回这个最小值若该结点的左半区间与 [ s , e ] [s,e] [s,e] 有交集即存在一段 [ s , x ] [s,x] [s,x] 与 [ l , m i d ] [l,mid] [l,mid] 有交集那么只需要满足 s m i d smid smid 即可随后查询左侧的最小值同理若该结点的右半区间与 [ s , e ] [s,e] [s,e] 有交集即存在一段 [ x , e ] [x,e] [x,e] 与 [ m i d 1 , r ] [mid1,r] [mid1,r] 有交集那么只需要满足 e m i d emid emid 即可随后查询右侧的最小值最后将左右两侧的最小值取最小值就是当前区间的最小值
void query(ll pos,ll l,ll r,ll s,ll e)
{if(sl re)return tree[pos];ll mid(lr)1,ansinf;if(smid)ansmin(ans,query(pos1,l,mid,s,e));if(emid)ansmin(ans,query(pos1|1,mid1,r,s,e));return ans;
}7.区间更新
假设此时修改的不只是一个元素的值比如将某一个区间内的所有值都加上 k k k这个时候就需要区间更新了。如果一个一个更新无疑是非常糟糕的还不如重建树。
所以我们可以借助区间查询的思想来进行。但这里有一个问题区间更新与查询不同这是会影响到某一整棵子树的值难道我们要每次都更新到叶子结点吗
为了优化这一过程我们引入一个新的数组懒惰标记。它被定义为当前区间所经历的且还没有向下传递的更新。用以累计这个区间所进行的改变在需要的时候才向下传递给子结点进行更新。
ll lazy[4*maxn];
void down(ll pos)
{if(lazy[pos]){lazy[pos1]lazy[pos];lazy[pos1|1]lazy[pos];tree[pos1]lazy[pos];tree[pos1|1]lazy[pos];lazy[pos]0;}
}
void update(ll pos,ll l,ll r,ll s,ll e,ll k)
{if(sl re){lazy[pos]k;tree[pos]k;return;}down(pos);ll mid(lr)1;if(smid)update(pos1,l,mid,s,e,k);if(emid)update(pos1|1,mid1,r,s,e,k);tree[pos]min(tree[pos1],tree[pos1|1]);
}二、树状数组
三、作业
1.黄题
P3372 【模板】线段树 1
P3870 [TJOI2009] 开关
P1816 忠诚
P1531 I Hate It
P5057 [CQOI2006] 简单题
2.绿题
P3373 【模板】线段树 2
