电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

ACM大牛总结的线段树专辑,超经典的

ACM大牛总结的线段树专辑,超经典的_第1页
1/21
ACM大牛总结的线段树专辑,超经典的_第2页
2/21
ACM大牛总结的线段树专辑,超经典的_第3页
3/21
【完全版】线段树 很早前写的那篇线段树专辑至今一直是本博客阅读点击量最大的一片文章,当时觉得挺自豪的,还去 pku 打广告,但是现在我自己都不太好意思去看那篇文章了,觉得当时的代码风格实在是太丑了,很多线段树的初学者可能就是看着这篇文章来练习的,如果不小心被我培养出了这么糟糕的风格,实在是过意不去,正好过几天又要给集训队讲解线段树,所以决定把这些题目重新写一遍,顺便把近年我接触到的一些新题更新上去~ ;并且学习了 splay 等更高级的数据结构后对线段树的体会有更深了一层,线段树的写法也就比以前飘逸,简洁且方便多了. 在代码前先介绍一些我的线段树风格:  maxn 是题目给的最大区间,而节点数要开 4 倍,确切的来说节点数要开大于 maxn 的最小2x的两倍  lson 和 rson 分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示  以前的写法是另外开两个个数组记录每个结点所表示的区间,其实这个区间不必保存,一边算一边传下去就行,只需要写函数的时候多两个参数,结合 lson 和 rson 的预定义可以很方便  PushUP(int rt)是把当前结点的信息更新到父结点  PushDown(int rt)是把当前结点的信息更新给儿子结点  rt 表示当前子树的根(root),也就是当前所在的结点 整理这些题目后我觉得线段树的题目整体上可以分成以下四个部分:  单点更新:最最基础的线段树,只更新叶子节点,然后把信息用 PushUP(int r)这个函数更新上来 o hdu1166 敌兵布阵 题意:O(-1) 思路:O(-1) 线段树功能:update:单点增减 query:区间求和 ?View Code CPP 1 2 3 4 5 6 7 8 9 10 11 12 13 #include #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 constint maxn =55555; int sum[maxn<<2]; void PushUP(int rt){ sum[rt]= sum[rt<<1]+ sum[rt<<1|1]; } void build(int l,int r,int rt){ if(l == r){ scanf("%d",&sum[rt]); return; 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 } int m =(l + r)>>1; build(lson); build(rson); PushUP(rt); } void update(int p,int add,int l,int r,int rt){ if(l ==...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

ACM大牛总结的线段树专辑,超经典的

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部