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进行平滑升级的实战指南(不中断服务版本更新)

Nginx进行平滑升级的实战指南(不中断服务版本更新)

《Nginx进行平滑升级的实战指南(不中断服务版本更新)》Nginx的平滑升级（也称为热升级）是一种在不停止服务的情况下更新Nginx版本或添加模块的方法,这种升级方式确保了服务的高可用性,避免了因升... 目录一.下载并编译新版Nginx1.下载解压2.编译二.替换可执行文件，并平滑升级1.替换可执行文件
阅读更多...
python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...
SQL Server跟踪自动统计信息更新实战指南

SQL Server跟踪自动统计信息更新实战指南

《SQLServer跟踪自动统计信息更新实战指南》本文详解SQLServer自动统计信息更新的跟踪方法,推荐使用扩展事件实时捕获更新操作及详细信息,同时结合系统视图快速检查统计信息状态,重点强调修... 目录SQL Server 如何跟踪自动统计信息更新：深入解析与实战指南 核心跟踪方法1️⃣ 利用系统目录
阅读更多...
Python操作PDF文档的主流库使用指南

Python操作PDF文档的主流库使用指南

《Python操作PDF文档的主流库使用指南》PDF因其跨平台、格式固定的特性成为文档交换的标准,然而,由于其复杂的内部结构,程序化操作PDF一直是个挑战,本文主要为大家整理了Python操作PD... 目录一、 基础操作1.PyPDF2 (及其继任者 pypdf)2.PyMuPDF / fitz3.Fre
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...
MySQL 强制使用特定索引的操作

MySQL 强制使用特定索引的操作

《MySQL强制使用特定索引的操作》MySQL可通过FORCEINDEX、USEINDEX等语法强制查询使用特定索引,但优化器可能不采纳,需结合EXPLAIN分析执行计划,避免性能下降,注意版本差异... 目录1. 使用FORCE INDEX语法2. 使用USE INDEX语法3. 使用IGNORE IND
阅读更多...
Python使用openpyxl读取Excel的操作详解

Python使用openpyxl读取Excel的操作详解

《Python使用openpyxl读取Excel的操作详解》本文介绍了使用Python的openpyxl库进行Excel文件的创建、读写、数据操作、工作簿与工作表管理,包括创建工作簿、加载工作簿、操作... 目录1 概述1.1 图示1.2 安装第三方库2 工作簿 workbook2.1 创建：Workboo
阅读更多...
SpringBoot中六种批量更新Mysql的方式效率对比分析

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种
阅读更多...
Ubuntu 24.04启用root图形登录的操作流程

Ubuntu 24.04启用root图形登录的操作流程

《Ubuntu24.04启用root图形登录的操作流程》Ubuntu默认禁用root账户的图形与SSH登录,这是为了安全,但在某些场景你可能需要直接用root登录GNOME桌面,本文以Ubuntu2... 目录一、前言二、准备工作三、设置 root 密码四、启用图形界面 root 登录1. 修改 GDM 配
阅读更多...
JSONArray在Java中的应用操作实例

JSONArray在Java中的应用操作实例

《JSONArray在Java中的应用操作实例》JSONArray是org.json库用于处理JSON数组的类,可将Java对象（Map/List）转换为JSON格式,提供增删改查等操作,适用于前后端... 目录1. jsONArray定义与功能1.1 JSONArray概念阐释1.1.1 什么是JSONA
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2