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。

相关文章

Linux使用fdisk进行磁盘的相关操作

Linux使用fdisk进行磁盘的相关操作

《Linux使用fdisk进行磁盘的相关操作》fdisk命令是Linux中用于管理磁盘分区的强大文本实用程序,这篇文章主要为大家详细介绍了如何使用fdisk进行磁盘的相关操作,需要的可以了解下... 目录简介基本语法示例用法列出所有分区查看指定磁盘的区分管理指定的磁盘进入交互式模式创建一个新的分区删除一个存
阅读更多...
Golang操作DuckDB实战案例分享

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck
阅读更多...
C# 读写ini文件操作实现

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
阅读更多...
Python使用qrcode库实现生成二维码的操作指南

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log
阅读更多...
Java操作ElasticSearch的实例详解

Java操作ElasticSearch的实例详解

《Java操作ElasticSearch的实例详解》Elasticsearch是一个分布式的搜索和分析引擎,广泛用于全文搜索、日志分析等场景,本文将介绍如何在Java应用中使用Elastics... 目录简介环境准备1. 安装 Elasticsearch2. 添加依赖连接 Elasticsearch1. 创
阅读更多...
Redis缓存问题与缓存更新机制详解

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1
阅读更多...
java Stream操作转换方法

java Stream操作转换方法

《javaStream操作转换方法》文章总结了Java8中流(Stream)API的多种常用方法,包括创建流、过滤、遍历、分组、排序、去重、查找、匹配、转换、归约、打印日志、最大最小值、统计、连接、... 目录流创建1、list 转 map2、filter（）过滤3、foreach遍历4、groupingB
阅读更多...
Java操作PDF文件实现签订电子合同详细教程

Java操作PDF文件实现签订电子合同详细教程

《Java操作PDF文件实现签订电子合同详细教程》：本文主要介绍如何在PDF中加入电子签章与电子签名的过程,包括编写Word文件、生成PDF、为PDF格式做表单、为表单赋值、生成文档以及上传到OB... 目录前言：先看效果：1.编写word文件1.2然后生成PDF格式进行保存1.3我这里是将文件保存到本地后
阅读更多...
Linux Mint Xia 22.1重磅发布: 重要更新一览

Linux Mint Xia 22.1重磅发布: 重要更新一览

《LinuxMintXia22.1重磅发布:重要更新一览》Beta版LinuxMint“Xia”22.1发布，新版本基于Ubuntu24.04，内核版本为Linux6.8，这... linux Mint 22.1「Xia」正式发布啦！这次更新带来了诸多优化和改进，进一步巩固了 Mint 在 Linux 桌面
阅读更多...
Python使用Colorama库美化终端输出的操作示例

Python使用Colorama库美化终端输出的操作示例

《Python使用Colorama库美化终端输出的操作示例》在开发命令行工具或调试程序时,我们可能会希望通过颜色来区分重要信息,比如警告、错误、提示等,而Colorama是一个简单易用的Python库... 目录python Colorama 库详解：终端输出美化的神器1. Colorama 是什么？2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2