线段树之进阶

前记

哦看了上次的blog感觉自己是个傻子
讲不清楚阿西吧
不管了
这次的目标是
·线段树区间修改
·一些杂题
那么就开始吧

区间修改

先把原来的题面修改一下

如题,已知一个数列,你需要进行下面两种操作:
1.将某个数修改成x
2.求出某区间每一个数的和
3.将某个区间的数全部加上x
N<=100000,M<=100000

上次的blog讲过了单点的修改,但是实际的问题中并没有那么好,猥琐的出题人往往会让选手们修改区间
这时候
聪明机智勇敢的区间修改操作就出现了
我们需要给线段树的Node增加一个Flg值
那么现在的Node就是

struct Node {
    int key,flg;
}

这个样子
这个Flg的代表的意义就是就是
本节点的统计信息已经根据标记更新过,但是本节点的子节点仍需要进行更新。
当前节点和子节点需要更新,那么应该将标记下传,并且取消当前的标记。
多加一个操作

void PushDown(int now,int L_size,int R_size) { //now表示需要进行操作的节点,L_size表示左子树代表的区间大小,R_size表示有子树代表的区间大小
    tree[Lson].key+=tree[now].flg*L_size,tree[Rson].key+=tree[now].flg*R_size;
    tree[Lson].flg+=tree[x].flg,tree[Rson].flg+=tree[x].flg;//考虑到子节点的之前的flg可能并没有更新过,所以用+=不会对以前的flg造成影响
    tree[now].flg=0;
}

显而易见这个操作是O(1)的
而区间修改就是依赖flg来实现的
专心看博客!
这是初始状态(原谅巨丑无比的图)
接下来将2-4区间都加上1
线段树变成
专心看博客!
这样
而查询的时候只需要每到一个节点就将标记下传,就可以保证遍历到的区域的线段树节点key值是正确的
接下来是区间修改的代码

void UpdateUp(int now,int L,int R,int QL,int QR,int p) {//now,L,R同单点修改,QL,QR表示修改的区间的左右边界,p表示所需要增加的值
    if (L==QL&&R==QR){tree[now].key+=(R-L+1)*p,tree[now].flg+=p;return;}//如果修改区间和当前区间重合,更行key和flg
    int mid=((R-L)>>1)+L;
    PushDown(now,mid-L+1,R-mid);//标记下传,保证key的正确
    if (QR<=mid) UpdateUp(Lson,L,mid,QL,QR,p);else
    if (QL>mid) UpdateUp(Rson,mid+1,R,QL,QR,p);else
    UpdateUp(Lson,L,mid,QL,mid,p),UpdateUp(Rson,mid+1,R,mid+1,QR,p);
    tree[now].key=tree[Lson].key+tree[Rson].key;
}   

那区间修改就是这个样子了
然后在进行查询的时候也要进行PushDown
代码如下

int Query(int now,int L,int R,int QL,int QR){//now为当前节点编号 L为当前节点所表示的区间的左边界,R为右边界 QL为询问区间的左边界 QR为询问区间的右边界 
        if (L==QL&&R==QR){return tree[now].key;}
        int mid=((R-L)>>1)+L;
        PushDown(now,mid-L+1,R-mid);
        if (QL<=mid&&QR<=mid) return Query(now<<1,L,mid,QL,QR);
    else if (QL>mid&&QR>mid) return Query((now<<1)|1,mid+1,R,QL,QR);
    else return Query(now<<1,L,mid,QL,mid)+Query((now<<1)|1,mid+1,R,mid+1,QR);
    } 

没错只加了PushDown
就是这么简单
ok
单点修改最好也进行PushDown
代码如下

void Update(int now,int L,int R,int x,int p){//now为当前节点编号 L为当前节点所表示的区间的左边界,R为右边界 x为要修改的序列中的数的编号 p为要加上的数 
        if (L==R&&L==x){tree[now].key=p;return;}
        int mid=((R-L)>>1)+L;
        PushDown(now,mid-L+1,R-mid);
        if (x<=mid) Update(now<<1,L,mid,x,p);else Update((now<<1)|1,mid+1,R,x,p);
        tree[now].key=tree[now<<1].key+tree[(now<<1)|1].key;
    }

总的来讲
闲着就PushDown就行了
就算不需要PushDown经行了也不会错
#杂题

题目来源不晓得……
如果出题人不高兴 侵权立删
……
还有杂题什么的,以后MayBe会更新,不过都懂得,这种东西随缘

No1

给定一课N节点的树,开始时每条边权为1
进行M次操作
操作有两种
1. 询问一个点到根的路径上的边权和
2. 把一条边的边权从1变成0
N<=2.510^5,M<=2.510^5

题意如上
emmmmmmm
思考下在看题解?
嘛,其实对于一条边的权修改只对其子树的答案有影响
然后
在dfs序上子树的ID是连续的
那么按照dfs建立线段树
每次修改一条边的时候对其子树的答案在线段树上经行区间修改
询问就是单点的询问
Get到没?
没有可以私信……
代码没写,不是我懒,是这道题是哪里的我都不知道……
如果那个dalao知道麻烦评论
废话有点多了
就先这样

后记

会出现错误,Maybe……
如有错误欢迎指出,谢谢!

“线段树之进阶”的14个回复

  1. Diarrhea With Amoxicillin Colchicine Products For Sale Cytotec Udi bayer levitra Super Kamagra Deutschland Purchase Orlistat Buy levitra in europe xenical 60 mg Erfahrungsbericht Viagra 100 Best Viagra Pills tadalafil cialis from india buy accutane online fast delivery Cialis Super Active Comprar Barato Indie Propecia Propecia Dosis Efectos Adversos Amoxicillin Pediatric Tab viagra Levitra Rivenditori Cialis Gр с–рўв˜nstig Kaufen 40mg

发表评论