uscao 线段树成段更新操作及Lazy思想（POJ3468解题报告）

2023-12-15 15:58
文章标签 操作 更新 报告 思想 lazy 解题 线段 poj3468 uscao 树成

本文主要是介绍uscao 线段树成段更新操作及Lazy思想（POJ3468解题报告），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

线段树成段更新操作及Lazy思想（POJ3468解题报告）

标签： treequerybuildn2cstruct
2011-11-03 20:37  5756人阅读  评论(0)  收藏  举报
  分类：
 

版权声明：本文为博主原创文章，未经博主允许不得转载。

就直接那POJ上面的例题来说吧，http://poj.org/problem?id=3468。

此题题意很好懂：

 给你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子节点的值的时候才去更新，这样避免许多可能无用的操作，从而节省时间 。

下面通过具体的代码来说明之。（此处的函数名和宏学习了小HH的代码风格）

在此先介绍下代码中的函数说明：

#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),也就是当前所在的结点

[cpp]  view plain copy
print ?
  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操作主要就是用在这里

[cpp]  view plain copy
print ?
  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()函数更新子节点的数值。

[cpp]  view plain copy
print ?
  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的关键。

接着就是update操作的三个if语句了，这里我曾经一直不理解，多亏nyf队友的指点，借此感谢之。


下面再解释query函数，也就是用这个函数来求区间和

[cpp]  view plain copy
print ?
  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：今天总算是对线段树入门了。

这里推荐一下，完全版线段树网址

下面贴出POJ3468完整的代码http://www.notonlysuccess.com/index.php/segment-tree-complete/，这里面有很飘逸的线段树代码，表示其update和query写的很巧妙，代码量也比较少，大家可以去学习。

[cpp]  view plain copy
print ?
  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. }  

这篇关于uscao 线段树成段更新操作及Lazy思想（POJ3468解题报告）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/497011。

相关文章

Nginx更新SSL证书的实现步骤

Nginx更新SSL证书的实现步骤

《Nginx更新SSL证书的实现步骤》本文主要介绍了Nginx更新SSL证书的实现步骤,包括下载新证书、备份旧证书、配置新证书、验证配置及遇到问题时的解决方法,感兴趣的了解一下... 目录1 下载最新的SSL证书文件2 备份旧的SSL证书文件3 配置新证书4 验证配置5 遇到的http://www.cppc
阅读更多...
MySQL游标和触发器的操作流程

MySQL游标和触发器的操作流程

《MySQL游标和触发器的操作流程》本文介绍了MySQL中的游标和触发器的使用方法,游标可以对查询结果集进行逐行处理,而触发器则可以在数据表发生更改时自动执行预定义的操作,感兴趣的朋友跟随小编一起看看... 目录游标游标的操作流程1. 定义游标2.打开游标3.利用游标检索数据4.关闭游标例题触发器触发器的基
阅读更多...
在C#中分离饼图的某个区域的操作指南

在C#中分离饼图的某个区域的操作指南

《在C#中分离饼图的某个区域的操作指南》在处理Excel饼图时,我们可能需要将饼图的各个部分分离出来,以使它们更加醒目,Spire.XLS提供了Series.DataFormat.Percent属性,... 目录引言如何设置饼图各分片之间分离宽度的代码示例：从整个饼图中分离单个分片的代码示例：引言在处理
阅读更多...
Python列表的创建与删除的操作指南

Python列表的创建与删除的操作指南

《Python列表的创建与删除的操作指南》列表（list）是Python中最常用、最灵活的内置数据结构之一,它支持动态扩容、混合类型、嵌套结构,几乎无处不在,但你真的会创建和删除列表吗,本文给大家介绍... 目录一、前言二、列表的创建方式1. 字面量语法（最常用）2. 使用list()构造器3. 列表推导式
阅读更多...
Go异常处理、泛型和文件操作实例代码

Go异常处理、泛型和文件操作实例代码

《Go异常处理、泛型和文件操作实例代码》Go语言的异常处理机制与传统的面向对象语言（如Java、C#）所使用的try-catch结构有所不同,它采用了自己独特的设计理念和方法,：本文主要介绍Go异... 目录一：异常处理常见的异常处理向上抛中断程序恢复程序二：泛型泛型函数泛型结构体泛型切片泛型 map三：文
阅读更多...
MySQL基本表查询操作汇总之单表查询+多表操作大全

MySQL基本表查询操作汇总之单表查询+多表操作大全

《MySQL基本表查询操作汇总之单表查询+多表操作大全》本文全面介绍了MySQL单表查询与多表操作的关键技术,包括基本语法、高级查询、表别名使用、多表连接及子查询等,并提供了丰富的实例,感兴趣的朋友跟... 目录一、单表查询整合（一）通用模版展示（二）举例说明（三）注意事项（四）Mapper简单举例简单查询
阅读更多...
Nginx概念、架构、配置与虚拟主机实战操作指南

Nginx概念、架构、配置与虚拟主机实战操作指南

《Nginx概念、架构、配置与虚拟主机实战操作指南》Nginx是一个高性能的HTTP服务器、反向代理服务器、负载均衡器和IMAP/POP3/SMTP代理服务器,它支持高并发连接,资源占用低,功能全面且... 目录Nginx 深度解析：概念、架构、配置与虚拟主机实战一、Nginx 的概念二、Nginx 的特点
阅读更多...
MySQL 数据库进阶之SQL 数据操作与子查询操作大全

MySQL 数据库进阶之SQL 数据操作与子查询操作大全

《MySQL数据库进阶之SQL数据操作与子查询操作大全》本文详细介绍了SQL中的子查询、数据添加（INSERT）、数据修改（UPDATE）和数据删除（DELETE、TRUNCATE、DROP）操作... 目录一、子查询：嵌套在查询中的查询1.1 子查询的基本语法1.2 子查询的实战示例二、数据添加：INSE
阅读更多...
使用Python在PDF中绘制多种图形的操作示例

使用Python在PDF中绘制多种图形的操作示例

《使用Python在PDF中绘制多种图形的操作示例》在进行PDF自动化处理时,人们往往首先想到的是文本生成、图片嵌入或表格绘制等常规需求,然而在许多实际业务场景中,能够在PDF中灵活绘制图形同样至关重... 目录1. 环境准备2. 创建 PDF 文档与页面3. 在 PDF 中绘制不同类型的图形python
阅读更多...
Java 操作 MinIO详细步骤

Java 操作 MinIO详细步骤

《Java操作MinIO详细步骤》本文详细介绍了如何使用Java操作MinIO,涵盖了从环境准备、核心API详解到实战场景的全过程,文章从基础的桶和对象操作开始,到大文件分片上传、预签名URL生成... 目录Java 操作 MinIO 全指南：从 API 详解到实战场景引言：为什么选择 MinIO？一、环境
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2