标题：重拾线段树
出处：Felix021
时间：Sun, 17 Jul 2016 22:46:33 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?2164

内容：
　　前几天讨论遇到一个涉及区间覆盖的数据统计，发现很适合使用线段树来解决，于是重新回顾了一下这个好几年前学过的东西，凭着残存的理解，好了好久才勉强写了出来，感觉自己确实是没有搞算法的天赋，在边界处理的时候磕磕碰碰的，需要改好几次才能写对，不够干净利落。

　　不过能从繁杂的业务中抽出来写写纯粹的数据结构和算法，有点回到学校的状态，感觉也蛮不错。

　　以前在学校折腾算法的时候，从yyt同学的分享的ppt学到了这个数据结构，印象比较深的是，ppt上说，对于一个长度是 x 的线段，使用数组（元素 i 的左右节点分别是 2*i 和 2*i+1 ）来记录的话，需要大小约为 3*x 的数组，但是在实际做题的时候却发现越界了，后来仔细去挖这个地方，才发现，其实应该是找到一个 y = 2^n 满足 2^(n-1) < x 


Generated by Bo-blog 2.1.0