线段树区间更新操作及Lazy思想(详解)

此题题意很好懂:  给你N个数,Q个操作,操作有两种,‘Q a b ’是询问a~b这段数的和,‘C a b c’是把a~b这段数都加上c。 需要用到线段树的,update:成段增减,query:区间求和 介绍Lazy思想:lazy-tag思想,记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 在此通俗的解释我理解的Lazy意思,比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,它的节点标记为rt,这时tree[rt].l== a && tree[rt].r == b 这时我们可以一步更新此时rt节点的sum[rt]的值,sum[rt] += c* (tree[rt].r - tree[rt].l + 1),注意关键的时刻来了,如果此时按照常规的线段树的update操作,这时候还应该更新rt子节点的sum[]值,而Lazy思想恰恰是暂时不更新rt子节点的sum[]值,到此就return,直到下次需要用到rt子节点的值的时候才去更新,这样避免许多可能无用的操作,从而节省时间。 下面通过具体的代码来说明之。 在此先介绍下代码中的函数说明:

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

 宏定义左儿子lson和右儿子rson,貌似用宏的速度要慢。 PushUp(rt):通过当前节点rt把值递归向上更新到根节点 PushDown(rt):通过当前节点rt递归向下去更新rt子节点的值 rt表示当前子树的根(root),也就是当前所在的结点

1 __int64 sum[N<<2],add[N<<2];
2 struct Node
3 {
4     int l,r;
5     int mid()
6     {
7         return (l+r)>>1;
8     }
9 } tree[N<<2];

这里定义数据结构sum用来存储每个节点的子节点数值的总和,add用来记录该节点的每个数值应该加多少 tree[].l tree[].r分别表示某个节点的左右区间,这里的区间是闭区间 下面直接来介绍update函数,Lazy操作主要就是用在这里

 1 void update(int c,int l,int r,int rt)//表示对区间[l,r]内的每个数均加c,rt是根节点
 2 {
 3     if(tree[rt].l == l && r == tree[rt].r)
 4     {
 5         add[rt] += c;
 6         sum[rt] += (__int64)c * (r-l+1);
 7         return;
 8     }
 9     if(tree[rt].l == tree[rt].r) return;
10     PushDown(rt,tree[rt].r - tree[rt].l + 1);
11     int m = tree[rt].mid();
12     if(r <= m) update(c,l,r,rt<<1);
13     else if(l > m) update(c,l,r,rt<<1|1);
14     else
15     {
16         update(c,l,m,rt<<1);
17         update(c,m+1,r,rt<<1|1);
18     }
19     PushUp(rt);
20 }

if(tree[rt].l == l && r == tree[rt].r) 这里就是用到Lazy思想的关键时刻 正如上面说提到的,这里首先更新该节点的sum[rt]值,然后更新该节点具体每个数值应该加多少即add[rt]的值,注意此时整个函数就运行完了,直接return,而不是还继续向子节点继续更新,这里就是Lazy思想,暂时不更新子节点的值。 那么什么时候需要更新子节点的值呢?答案是在某部分update操作的时候需要用到那部分没有更新的节点的值的时候,这里可能有点绕口。这时就掉用PushDown()函数更新子节点的数值。

 1 void PushDown(int rt,int m)
 2 {
 3     if(add[rt])
 4     {
 5         add[rt<<1] += add[rt];
 6         add[rt<<1|1] += add[rt];
 7         sum[rt<<1] += add[rt] * (m - (m>>1));
 8         sum[rt<<1|1] += add[rt] * (m>>1);
 9         add[rt] = 0;//更新后需要还原
10     }
11 }

PushDown就是从当前根节点rt向下更新每个子节点的值,这段代码读者可以自己好好理解,这也是Lazy的关键。  下面再解释query函数,也就是用这个函数来求区间和

 1 __int64 query(int l,int r,int rt)
 2 {
 3     if(l == tree[rt].l && r == tree[rt].r)
 4     {
 5         return sum[rt];
 6     }
 7     PushDown(rt,tree[rt].r - tree[rt].l + 1);
 8     int m = tree[rt].mid();
 9     __int64 res = 0;
10     if(r <= m) res += query(l,r,rt<<1);
11     else if(l > m) res += query(l,r,rt<<1|1);
12     else
13     {
14        res += query(l,m,rt<<1);
15        res += query(m+1,r,rt<<1|1);
16     }
17     return res;
18 }

第一个if还是区间的判断和前面update的一样,到这里就可以知道答案了,所以就直接return。 接下来的查询就需要用到rt子节点的值了,由于我们用了Lazy操作,这段的数值还没有更新,因此我们需要调用PushDown函数去更新之,满足if(add[rt])就说明还没有更新。 到这里整个Lazy思想就算介绍结束了,可能我的语言组织不是很好,如果有不理解的地方可以给我留言,我再解释大家的疑惑。 PS:今天总算是对线段树入门了。

附上此题的代码:

  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 const int N = 100005;
  5 #define lson l,m,rt<<1
  6 #define rson m+1,r,rt<<1|1
  7 
  8 __int64 sum[N<<2],add[N<<2];
  9 struct Node
 10 {
 11     int l,r;
 12     int mid()
 13     {
 14         return (l+r)>>1;
 15     }
 16 } tree[N<<2];
 17 
 18 void PushUp(int rt)
 19 {
 20     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
 21 }
 22 
 23 void PushDown(int rt,int m)
 24 {
 25     if(add[rt])
 26     {
 27         add[rt<<1] += add[rt];
 28         add[rt<<1|1] += add[rt];
 29         sum[rt<<1] += add[rt] * (m - (m>>1));
 30         sum[rt<<1|1] += add[rt] * (m>>1);
 31         add[rt] = 0;
 32     }
 33 }
 34 
 35 void build(int l,int r,int rt)
 36 {
 37     tree[rt].l = l;
 38     tree[rt].r = r;
 39     add[rt] = 0;
 40     if(l == r)
 41     {
 42         scanf("%I64d",&sum[rt]);
 43         return ;
 44     }
 45     int m = tree[rt].mid();
 46     build(lson);
 47     build(rson);
 48     PushUp(rt);
 49 }
 50 
 51 void update(int c,int l,int r,int rt)
 52 {
 53     if(tree[rt].l == l && r == tree[rt].r)
 54     {
 55         add[rt] += c;
 56         sum[rt] += (__int64)c * (r-l+1);
 57         return;
 58     }
 59     if(tree[rt].l == tree[rt].r) return;
 60     PushDown(rt,tree[rt].r - tree[rt].l + 1);
 61     int m = tree[rt].mid();
 62     if(r <= m) update(c,l,r,rt<<1);
 63     else if(l > m) update(c,l,r,rt<<1|1);
 64     else
 65     {
 66         update(c,l,m,rt<<1);
 67         update(c,m+1,r,rt<<1|1);
 68     }
 69     PushUp(rt);
 70 }
 71 
 72 __int64 query(int l,int r,int rt)
 73 {
 74     if(l == tree[rt].l && r == tree[rt].r)
 75     {
 76         return sum[rt];
 77     }
 78     PushDown(rt,tree[rt].r - tree[rt].l + 1);
 79     int m = tree[rt].mid();
 80     __int64 res = 0;
 81     if(r <= m) res += query(l,r,rt<<1);
 82     else if(l > m) res += query(l,r,rt<<1|1);
 83     else
 84     {
 85        res += query(l,m,rt<<1);
 86        res += query(m+1,r,rt<<1|1);
 87     }
 88     return res;
 89 }
 90 
 91 int main()
 92 {
 93     int n,m;
 94     while(~scanf("%d %d",&n,&m))
 95     {
 96         build(1,n,1);
 97         while(m--)
 98         {
 99             char ch[2];
100             scanf("%s",ch);
101             int a,b,c;
102             if(ch[0] == 'Q')
103             {
104                 scanf("%d %d", &a,&b);
105                 printf("%I64d\n",query(a,b,1));
106             }
107 
108             else
109             {
110                 scanf("%d %d %d",&a,&b,&c);
111                 update(c,a,b,1);
112             }
113         }
114     }
115     return 0;
116 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吾爱乐享

short s=1;s=s+1; short s=1;s+=1; 有区别么?? 如果有的话区别是什么?

15930
来自专栏java一日一条

教你在Java接口中定义方法

基本上所有的Java教程都会告诉我们Java接口的方法都是public、abstract类型的,没有方法体的。

9410
来自专栏积累沉淀

JDK动态代理的底层实现原理

JDK动态代理的底层实现原理      动态代理是许多框架底层实现的基础,比如Spirng的AOP等,其实弄清楚了动态代理的实现原理,它就没那么神奇了,下面就来...

60770
来自专栏PHP在线

PHP中正则表达式学习及应用

正则表达式元字符 * 匹配前一个内容的0次1次或多次 . 匹配内容的0次1次或多次,但不包含回车换行 + 匹配前一个内容的1次或多次 ?匹配前一个内容...

33880
来自专栏玩转JavaEE

MongoDB固定集合

一般情况下我们创建的集合是没有大小的,可以一直往里边添加文档,这种集合可以动态增长,MongoDB中还有一种集合叫做固定集合,这种集合的大小是固定的,我可以在创...

34470
来自专栏刘君君

JVM Specification notes 1 -Jvm Structure

摘要: Jvm Structure 正文: Java 虚拟机结构 Class文件格式 数据类型 原始类型(基本类型) 数值类型{整数[byte8 short1...

38070
来自专栏友弟技术工作室

Go 程序的基本结构和要素

示例 package main import "fmt" func main() { fmt.Println("hello, world") } 包...

336110
来自专栏编程

linux基础(三)

一、文本处理工具 1、文本查看工具less和cat cat -E filename 能看到行的结束符 -A filename 能看到tab键 回车 (hexdu...

29970
来自专栏码云1024

c++模板与泛型编程

30530
来自专栏专注数据中心高性能网络技术研发

HERD--GCC宏

减少跳转语句失效时CPU等待取指令时间,提高CPU效率 使用__builtin_expect(EXP,N) 意思是EXP==N的概率很大 一般封装为LIKELY...

30250

扫码关注云+社区

领取腾讯云代金券