线段树懒惰点标记更新hduhdu-1698justahook

关键词：

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1698

题意：自行读题

解题思想：线段树原更新一次只能更新一个叶子节点，并更新此叶子结点以上所有相关的点，当一个区间做相同更新时，叶子节点以上的相关节点不断更新，时间复杂度增加。为节省时间，为每个点添加懒惰标记。自定义节点范围（l,r为求子节点区间和），懒惰点标记（lazy储存变化值），节点和（value节点区间和）。具体实现过程：当更新一个区间时，标记该区间的父亲节点为懒惰区间（祖宗节点的值不用标记，只要更新），同时更新涵盖该区间的节点，而该区间暂时懒得去更新，等下一次更新的区间与原被标记的区间有重合时，则此时将原标记区间往下标记并更新，同时父亲节点因为更新了，没懒惰了，则取消懒惰标记，即懒惰标记传给了子节点，直到重合区间可以以子节点为单位时就可以偷懒不用往下更新了，然后以相同懒惰更新的方式更新这次要更新的区间。

样例代码图解：

下图为初始化树，圈内为value值，下标为范围。

 第一次更新后1-5更新为2时后的树，红色为标记点，发现1-5的子节点并没有更新，因为计算总和只和1-5这个点有关，更新这个点就行了。

 第二次更新：在访问点5-9时发现5所在的1-5点被标记了，标记点下推，并更新子节点的值。

 第二次5-9区间更新后的树以及标记的点。

 根据图一下子就可以看出懒惰标记的意思来了，结合代码就方便多了，我画了很久的图QAQ。

具体代码如下：

#include<bits/stdc++.h>

const int maxn=100000;
using namespace std;

struct nodetree
    int l,r;
    int value,lazy;
tree[maxn<<2];

void pushup(int now)

    tree[now].value=tree[now<<1].value+tree[now<<1|1].value;


void build(int l,int r,int n)

    tree[n].l=l;
    tree[n].r=r;
    tree[n].lazy=0;
    if(l==r)
    
        tree[n].value=1;
        return;
    
    int mid=(l+r)>>1;
    build(l,mid,n<<1);
    build(mid+1,r,n<<1|1);
    pushup(n);

void pushdown(int n)

    if(tree[n].lazy!=0)
    
        tree[n<<1].lazy=tree[n<<1|1].lazy=tree[n].lazy;
        tree[n<<1].value=(tree[n<<1].r-tree[n<<1].l+1)*tree[n<<1].lazy;
        tree[n<<1|1].value=(tree[n<<1|1].r-tree[n<<1|1].l+1)*tree[n<<1|1].lazy;
        tree[n].lazy=0;
    

void update(int l,int r,int le,int ri,int n,int va)

    if(r<le||l>ri)
        return;
    if(l>=le&&r<=ri)
    
        tree[n].lazy=va;
        tree[n].value=tree[n].lazy*(tree[n].r-tree[n].l+1);
        return;
    
    pushdown(n);
    int mid=(l+r)>>1;
    if(mid>=le) update(l,mid,le,ri,n<<1,va);
    if(mid<ri) update(mid+1,r,le,ri,n<<1|1,va);
    pushup(n);

int main()

    int T;
    while(~scanf("%d",&T))
    
        int count=1;
        while(T--)
        
            int n,t,l,r,va;
            scanf("%d",&n);
            build(1,n,1);
            scanf("%d",&t);
            while(t--)
            
                scanf("%d %d %d",&l,&r,&va);
                update(1,n,l,r,1,va);
            
            printf("Case %d: The total value of the hook is %d.
",count++,tree[1].value);
        
    
    return 0;

　　最后说一下点的value是通过数学计算算出来的。

hdu1698justahook线段树区间更新

 　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1698　　题目描述：区间更新，最后求出1~n之和　　　　解题思路：这里涉及到区间更新，这也是我第一次写区间更新，以前都是单点更新，回溯就可以了，如果将区间更... 查看详情

数据结构线段树（区间修改/区间求和）(代码片段)

...求和的问题】区间求和部分内容与上一篇内容相同，详见线段树点修改/区间求和已经知道了在O(logN)的复杂度内求N个连续数之和的做法对于区间修改，最简单的办法就是进行多次点修改但是多次点修改最后的时间复杂度为O(NlogN)... 查看详情

[hdoj3911]blackandwhite（线段树，区间合并）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3911题意：一个01串，两种操作：0ab：查询[a,b]内连续1的最长长度。1ab：翻转[a,b]内的所有数字（0变1，1变0）。更新操作落实到具体数字，这时候不能莽直接更新数字对吧，我们要考虑翻... 查看详情

线段树及其基本操作

...惰标记了解一下，其余略 实现步骤：略 备注：在线段树里，单点更新与单点累加和树状数组上的单点跟新有区别，树状数组还需与原数组求差值，线段树不用。线段树的区间求最值差别不大，在此贴一份A过题的最值代... 查看详情

线段树模板(代码片段)

https://oi-wiki.org/ds/seg/poj3468区间增减值，区间和。线段树思想：利用二叉树将每一个区间所需要的值都记录下来。lazy思想：延迟对叶子节点的修改，要用到的时候才真的去修改，lazy数组记录修改的值。#include<iostream>#include<... 查看详情

bzoj3476-懒惰的奶牛线段树

题解：感觉这题和别人的做法不一样。。。呵呵呵。。。调了一百年。。设家坐标为（a,b），对于每个点（x,y），可以转化为|a-x|+|b-y|<=k对于每个点，它的影响范围是一个菱形（也就是一个正方形啦。。），也就是一个图上有... 查看详情

线段树入门（汇总）(代码片段)

标签：线段树这篇文章主要内容主要来自NotOnlySuccess大神若干年前博客中的博文《【完全版】线段树》，由于时间有些久远，现在已经找不到大神的原博文了，所以整理了一些网上的资料，在这里还原一下。代码风格maxn是题目给... 查看详情

线段树(代码片段)

1、什么是线段树？线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(log... 查看详情

线段树(代码片段)

1、什么是线段树？线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(log... 查看详情

bzoj.3064.cpu监控(线段树历史最值)

...求支持查询[l,r]的最值、历史最值，区间加/重设(Solution)线段树，每个点再维护一个历史(从0到现在)最大值、历史(从上次下传标记到现在)最大的set,add标记PushDown时肯定是先下放历史标记，之后再用当前标记更新/*要记得当要PushDow... 查看详情

杭电hduacm1698justahook（线段树区间更新延迟标记）

欢迎“热爱编程”的高考少年——报考杭州电子科技大学计算机学院JustaHookTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):20889    AcceptedSubmission 查看详情

p2023[ahoi2009]维护序列-线段树区间乘法加法(代码片段)

记得及时更新sum（每次修改都更新），写成一个update函数比较好，因为很多时候会忘了%还有懒标记是标记在这个点本身上的然后就是左儿子和右儿子一定要看清楚。。。一个是n*2，一个是n*2+1，涉及到这部分的代码一定要专注乘... 查看详情

hdu1698justahook线段树+成段更新+lazy标记

JustaHookTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):15889    AcceptedSubmission(s):7897ProblemDescriptionInth 查看详情

[uva11992]fastmatrixoperations（多延迟标记，二维线段树，区间更新）

...子矩阵和、最小值、最大值n很小(<=20)，所以可以开20棵线段树，每次操作按行更新。特别小心put和add两个延迟标记，坑老惨了。put初始化-1最简单的坑，略过。build的时候要每一个节点都要clear，不能只clear叶 查看详情

线段树标记永久化

前言对于树套树，主席树等使用到线段树的比较复杂的数据结构，如果区间修改的话，打标记后pushdown或者pushup是很难做到的完全不行吧所以这个时候，一个神奇的东西诞生了。。。正题线段树标记永久化，维护一个标记，假设... 查看详情

计蒜客-lplandenergy-savinglamps线段树+点更新(代码片段)

Duringtea-drinking,princess,amongstotherthings,askedwhyhassuchagood-naturedandcuteDragonimprisonedLplintheCastle?Dragonsmiledenigmaticallyandansweredthatitisabigsecret.Afterapause,Dragonadded:—Wehavea 查看详情

p3373模板线段树2线段树，模板(代码片段)

OMG_Data_StructureSo_Interesting_Mother-Fucker（译：数据结构，奥妙重重）虽然只是模板，但还是挺麻烦的，可见数据结构都是毒瘤。 已知一个数列，你需要进行下面三种操作：操作1：格式：1xyk含义：将区间[x,y]内每个数乘上k操作2... 查看详情

colortheball线段树区间更新但点查询

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<sstream>#include<algorithm>#include<queue>#include<deque>#include<iomanip& 查看详情