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

相关文章

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,:本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

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