树状数组

首先树状数组,就是用数组来模拟树形结构.

和「堆」一样，树状数组的 0 号下标不放置元素，从 1 号下标开始使用。

这样命名的含义是截取一个正整数的二进制表示里的最低位的 1 和它后面的所有的 0。lowbit 的定义如下：

说明：

这里 x 一定是正整数，即 x >= 1；

这里 &表示按位与运算；

-x 也可以写成 (~x + 1) ，这里 ~ 表示「按位取反」。这是负数的定义，负数用补码表示，它的值等于这个负数的绝对值按位取反以后再加 11，因此

将离散过的数据,从后往前放进树状数组里,

当第 i 个数的时候,即将放进 树状数组 里的时候,后边比他小的数已经放进他前面的下标里了, 因此只需要把他前面元素的数量加一块,就得到后边有多少比第i个数小的了

当然是链表啦，这是链表的一大优势。 数组插入或删除后面的所有数据都要移位，栈只能插入到顶部，也只能删除顶部，任意位置的插入删除需要进行很多入栈出栈 *** 作。 链表的话，直接对相应位置的指针 *** 作就行了。

---