2017/9/14

课余时间看了看《挑战程序设计》这本书，对于线段树和树状数组的地方做出一定总结，其实现在看题目对于知识点的理解帮助更大，但我想再把知识点确定一下，之后总结题目，望老师理解

线段树是擅长处理区间的，树上的每个节点都维护一个区域，根维护的是整个区域，每个节点维护的是父亲的区间二等分后的其中一个子区间。常用于维护的数据有最大值、最小值、区间元素个数等，线段树最底层的元素一定是划分到不能再分的元素个体。

操作：

1、 给定s和t，求as、a(s+1)、… 、at的最小值

2、 给定i和x，把ai的值改成x

线段树使用：

首先需要添加节点，将区间不断划分直至不能再划分时插入该元素。

节点值的更新：当更新一个节点值，其之上的所有父节点的值都需要更新

节点值的查询：划定要查询的区间，当前区间在要查询区间时，保存维护值，完全不在区间时，返回函数。不完全在时通过递归不断划分现区间使其满足以上两者。

线段树复杂度：

基于线段树的RMQ的复杂度：n个元素的线段树每一次操作的复杂度都是O(logn)，在n个元素的线段树初始化的时间复杂度和空间复杂度都是O(n)

http://blog.****.net/zearot/article/details/48299459

 

 

树状数组的每个节点维护的是对应区间的和，用（从1到t的和）-（从1到s的和）来表示（s到t的和），即对于任意的i，都可以计算出1到i的部分和。

操作：

1、 给定i，计算a1+a2+ … +ai

2、 给定i和x，执行ai+=x

树状数组使用：

首先需要添加节点的值，直接用add()函数解决，即增加了ai的值，又维护的区间和

BIT值求和(sum函数)：使用i-=（i&-i）来计算i到i的节点值之和。

BIT值更新(add函数)：使用i+=(i&-i)来维护后面节点的值

树状数组复杂度：

在求和是总共需要对logn个数进行操作，所以复杂度也是O(logn)。

二维BIT：

建立一个W*H的二维BIT，直需要多加一个y方向上的BIT来管理每一个大小为W的x轴的BIT，这样所有的操作的复杂度都是O(logW*logH)。同样的方法可以扩展更高维度的情况。