4月15日更新
有个地方上次知识点讲述的时候说错了。线段树存储的空间是开了四倍。(我是蒟蒻,<<2应该是*4哈)
这样的话,推导也讲错了,按照最好情况讲的。
上次给同学们画的图是典型考虑的二叉树没有空间浪费的画法,没有考虑到完全二叉树画法。
而在一个二叉树中,最后一层的数量是上面所有层数的一倍+1,如果最后一层占用了一个就形成了最坏情况。即在元素少的情况下画出完全二叉树所占用的空间有很大一部分没有用到,而这一部分在进行线段树的修改和查询的时候可能会被访问到,所以需要(2n-1)+2n,大概就是4n的空间
推导参考链接:https://blog.csdn.net/qq_41441248/article/details/84325263?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-2.pc_relevant_antiscanv2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-2.pc_relevant_antiscanv2&utm_relevant_index=5
——————————————————————————————————————————————————————————————————————————————————
4月15日之前
手写了好多遍模板 ,在 一次次改错中理解了里面针对二分和懒惰标记的运用
先来说一下为什么要开两倍的 空间用来存储数据
看一下这个线段树的存储图,在图中,存了6个数的线段,用了11个空间。实际上在二分的过程中 分出了接近原来长度的空间 8 分 8 4 2 1 大概就是这样
这个图是最大值,我们需要去做其他操作时,只需要更变它合并的函数push_up
再说一下线段树和树状数组的区别:树状数组维护的前缀和,线段树维护的一个区间内
维护区间:需要更新改变的区间。
那么我们来分开剖析一下线段树:
先看建树有关操作
左右儿子这个就不必说了,二分嘛 右儿子 | 1操作是为了尽量保留多的数
push_up就是线段树存储什么样的数据,如果是存放最大值就把它做成求最值的函数
建树函数其实也很好理解,在二分的过程当中,如果l 碰到了 r 说明已经无法再分下去了,就让这个数作为一个叶子节点存储就可以了
剩下的操作就是二分,然后合并。这里就是分治算法的套路嘛。tag[p] 这个是懒惰标记,接下来说这个
//线段树初步建成 ll ls(ll p){//p的左儿子 return (p<<1); } ll rs(ll p){//p的右儿子 return (p<<1|1); } void push_up(ll p){//自底向上合并 ans[p]=ans[ls(p)]+ans[rs(p)]; } void build(ll p,ll l,ll r){ tag[p]=0; if(l==r){ ans[p]=a[l]; return ; } ll mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p); }
懒惰标记:懒惰标记实际上就是让子节点暂时处于不更新状态,用到的时候再更新,如本题中的visit[]就是懒惰标记, 例如总长度是1-10,我们现在要想更新1-6,(将1-6的值都加3)那么update()会先找1-10,发现不合适,再找他的左右孩子, 发现1<5,说明1-6的区间在1-10的左孩子中,同时6>5,1-6也在1-10的右孩子中,这样依次去找1-6在的区间。但是找到1-5的时候, 我们发现整个1-5都在1-6中间,也就是说这一段都要更新,那么我们将1-5的sum值更新了,同时用visit[rt]+=3记录下来1-5中的数字现在每个都要加的数字, 但是1-5下边还有1-3,4-5,3-3,4-4,5-5,这些我们就可以不用更新,因为这些我们暂时还用不到, 假如现在又要将1-5区间的值都加5,那么visit[rt]+=5,此时就是8了,但是还是不用更新他的子节点,假如我们现在要用到1-3区间了, 我们就可以一次性给1-3区间加上8,而不用先加3,再加5,这样懒惰标记就使得每次的递归都少了好多
void f(ll p,ll l,ll r,ll k){//消除一个懒标记 tag[p]+=k; ans[p]+=k*(r-l+1); } void push_down(ll p,ll l,ll r){//自顶向下消除懒标记 ll mid=(l+r)>>1; f(ls(p),l,mid,tag[p]); f(rs(p),mid+1,r,tag[p]); tag[p]=0; }维护区间的操作 及 求和操作
维护:判断对范围内的进行清除懒惰标记,然后消除下方的懒惰标记,再二分一下
求和:判断对范围内的区间值进行返回操作,消除标记再二分一下
void update(ll nl,ll nr,ll l,ll r,ll p,ll k){//维护区间【nl。。。nr】加k if(nl<=l&&r<=nr){ tag[p]+=k; ans[p]+=k*(r-l+1); return ; } push_down(p,l,r); ll mid=(l+r)>>1; if(mid>=nl)update(nl,nr,l,mid,ls(p),k); if(mid<nr)update(nl,nr,mid+1,r,rs(p),k); push_up(p); } ll query(ll q_l,ll q_r,ll l,ll r,ll p){//求q_l...q_r的区间和 ll res=0; if(q_l<=l&&r<=q_r){ return ans[p]; } // push_down(p,l,r); ll mid=(l+r)>>1; if(mid>=q_l)res+=query(q_l,q_r,l,mid,ls(p)); if(mid<q_r)res+=query(q_l,q_r,mid+1,r,rs(p)); return res; }
给出一下完整ac题的代码:
题目链接:https://www.luogu.com.cn/problem/P3372
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long const ll maxt = 100005; ll n,m; ll a[maxt]; ll ans[maxt<<2]; //因为使用了二分的原理,往后展开存储的时候浪费了一半的空间 ll tag[maxt<<2]; ll ls(ll p) { return p<<1; } ll rs(ll p) { return p<<1|1; } void f(ll p,ll l,ll r,ll k) { tag[p]+=k; ans[p]+=k*(r-l+1); } void push_up(ll p) { ans[p]= ans[ls(p)]+ans[rs(p)]; } void push_down(ll p,ll l,ll r) { ll mid = (l+r)>>1; f(ls(p),l,mid,tag[p]); f(rs(p),mid+1,r,tag[p]); tag[p]=0; } void build(ll p,ll l,ll r) { tag[p]=0; if(l==r) { ans[p] = a[l]; return ; } ll mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p); } void update(ll nl,ll nr,ll l ,ll r,ll p ,ll k) { if(l>=nl&&r<=nr) { tag[p]+=k; ans[p]+=k*(r-l+1); return; } push_down(p,l,r); ll mid = (l+r)>>1; if(mid>=nl) update(nl,nr,l,mid,ls(p),k); if(mid<nr) update(nl,nr,mid+1,r,rs(p),k);//如果mid<=nr,那么mid+1就会超过范围,就会re push_up(p); } ll query(ll nl,ll nr,ll l ,ll r,ll p) { ll res=0; if(l>=nl&&r<=nr) { return ans[p]; } push_down(p,l,r); ll mid = (l+r)>>1; if(mid>=nl) res+=query(nl,nr,l,mid,ls(p)); if(mid<nr) res+=query(nl,nr,mid+1,r,rs(p)); return res; } int main() { ll i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } build(1,1,n); for(i=1;i<=m;i++) { ll t,x,y,k; cin>>t; if(t==1) { cin>>x>>y>>k; update(x,y,1,n,1,k); } if(t==2) { cin>>x>>y; ll s = query(x,y,1,n,1); cout<<s<<endl; } } }
https://www.cnblogs.com/CeLaMbDa/p/10389876.html 这个博客提到了很多有疑问的地方,如果不明白里面的一些实现可以去看看