树状数组和线段树

树状数组

解决什么问题?

  • 给某个位置上的数，加上一个数。(单点修改)
  • 求某一个前缀和。（区间查询）

时间复杂度

  • O(long n)

步骤及实现

给定一个数组{1,5,7,11,4,3,2,6,11,21,15,17,14,13,20,35}。下面将通过树状数组的方式进行查询与修改。

  1. 把普通数组进行存储。

    存储的位置，从数组的下标”1”开始存，下标”0”不存储元素。

  2. 把普通数组转换成树状数组（重点）。

    看不懂没关系，先给大家讲解一下，单点修改和区间查询是如何方便的：

    • 树状数组的单点修改，对整体数组修改影响较小。
    “前缀和”的单点修改对整体数组修改的影响

    假如我们对一个数组的下标3的元素进行加3操作，那么它对应的前缀和数组，下标3之后的所有元素都要进行加3操作，这样操作的时间开销是极大的。

    如果使用树状数组，对下标3的元素进行加3操作，树状数组的开销就小得多。

    仅对下标为“3”,”4”,”8 “,“16”的元素进行加3操作。

    1. 下面是最终转换的树状数组：

    ​

    ​