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

2023-12-15 15:58

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

 

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

标签: treequerybuildn2cstruct
  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

相关文章

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)

《JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)》本文介绍了如何在Windows系统上配置多版本JDK(以JDK8和JDK17为例),并通过图文结合的方式给大家讲解了详细步骤,具有... 目录第一步 下载安装JDK第二步 配置环境变量第三步 切换JDK版本并验证可能遇到的问题前提:公司常