树状数组及其实现
引言
树状数组也是一种通过数组来表示树的结构，我们所熟悉的堆与完全二叉树通常也会使用这种方式实现，即，使用数组来表示树。至于完全二叉树(堆是一种特殊的完全二叉树)，树中元素之间的关系较为简单，主要是父节点与子节点之间的关系，这种关系在数组中我们可以通过下标来实现。例如，如果用数组表示一棵完全二叉树的时候，(下标从 1 开始)，对于下标为 \(i\) 的节点，左孩子节点为 \(2i\) 右孩子为 \(2i+1\) 。那么我们可以得出结论，完全二叉树的数组是用数组下标来表示节点之间的父子关系，树状数组不仅能够使用下标表示节点之间的父子关系，还可以表示一些节点(我们称之为区间) 之间的关系。
什么是树状数组
节点的意义与节点间的关系
与完全二叉树不同的是，完全二叉树我们的目的是将树映射到数组上，使用数组的下标来表示树中节点间的关系。个人觉得树的结构，本质是探究节点的关系，节点是关键，那么数组最重要的就是下标了。树状数组我个人的理解就是
在上图中，数组 \(A\) 表示原始数组，