树状数组的原理是什么?
来源:千锋教育
发布人:xqq
2023-10-14
推荐
在线提问>>
一、树状数组的原理
原理
树状数组的原理是，树状数组为了节省空间，删去了不必要的结点，将结点数压缩到与数组长度相同。方案是这样的：数组的每个位置代表其在图中垂直向上追溯可以达到的较高的结点。
树状数组可以解决什么问题
可以解决大部分区间上面的修改以及查询的问题，例如1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改，换言之，线段树能解决的问题，树状数组大部分也可以，但是并不一定都能解决，因为线段树的扩展性比树状数组要强。
树状数组和线段树的区别在哪
有人会问了既然线段树的问题能够用树状数组解决而且线段树还比树状数组扩展性强，那为什么不直接用线段树呢？问的很好，树状数组的作用就是为了简化线段树，举个例子：一个问题可以用线段树解决写代码半个小时，但是用树状数组只需要10分钟，那么你会选择哪一个算法呢?没错，基于某些简单的问题，我们没必要用到功能性强但实现复杂的线段树(杀鸡焉用宰牛刀)。
优缺点
优点：修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小，并且实现比线段树简单
缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决。
延伸阅读：
二、完全二叉树
完全二叉树是一种特殊的二叉树，满足以下要求：
所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边。 需要注意的是不要把完全二叉树和“满二叉树”搞混了，完全二叉树不要求所有树都有左右子树，但它要求：任何一个节点不能只有左子树没有右子树；叶子节点出现在最后一层或者倒数第二层，不能再往上。
