线段树 LeetCode 307
开了新的tag，主要用途一是激励我不断刷LC，第二是记录一下刷题过程中遇到的一些直线没有碰到过的、比较新奇/遗忘了的数据结构，以便之后复习~
307第一眼看上去我首先的思路就是积分图，但是只要稍微思考一下就会发现如果用积分图做的话在复杂度上和暴力没有任何区别。。。根本的问题就在积分图存储的同样是点位信息，时间复杂度上只是将sum的复杂度转移到了update上，总的复杂度依然是O(n)级别的
那么问题出在哪里呢？以往的经验告诉我，树/数组的每一个节点存储的都是点位信息，而从没想过将某一段的信息整合之后存储在一个点位中，以此构建出数据结构。事实上，如果有了这个思想，即使307不会线段树，也能快很多。
线段树
线段树在总体上继承树的特点：每一个叶子节点负责记录原始数组的点位信息。每个非叶子节点所代表的线段长度 d>1，代表的是其左右子节点的信息的区间加法。这里的区间加法所代表的不仅只加法。引用这篇文章的例子：
符合区间加法的例子：
- 数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和
- 最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD )
- 最大值——总最大值=max(左区间最大值，右区间最大值)
不符合区间加法的例子：
- 众数——只知道左右区间的众数，没法求总区间的众数
- 01序列的最长连续零——只知道左右区间的最长连续零，没法知道总的最长连续零
在线段树的构建上，有 自顶向下 和 自底向上 两种构建方法。
自底向上的方法相对比较简单，不用递归，优点在于树的构建、点位修改、区间查询都很快和易于理解。直接看LeetCode的官方题解就能理解和上手。目前我还想不出这种方法有什么缺点。
自顶向下的方法必须使用递归。可以查看这一篇博客。目前太懒了还没全部看完递归的解法，不过总体看来是没有非递归简洁和方便的。。
