树状数组理论基础

树状数组（binary indexed trees,二进制索引树），最早由Peter M. Fenwick于1994年以“A New Data Structure for Cumulative Frequency Tables"为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（cumulative frequency）的计算问题，现多用于高效计算数列的前缀和（∑ai）.它可以以O(㏒n)的时间得到（∑ai），并同样以O(㏒n)的时间执行对某项加一个常数的操作。

核心思想

  1）树状数组中的每一个元素是原数组中的一个或者多个连续元素的和。

   2）在进行连续求和操作a1+a2+....+an时，只需要将树状数组中某几个元素进行求和。

   3）在对某一个元素进行修改时，也只需要修改树状数组中某几个元素的和即可。

树状数组的结构

​

​

1）a是原始数据的树状数组。

2）数组e表示树状数组。图中任意一个元素ei是由多个或一个a中的元素的和构成的。

例如，e1=a1,e4=e2+a3+a4=e1+e2+e3+e4.

3)如果数字i的二进制表示中末尾有k个连续的0，则ei是a数组中连续2的k次方个元素的和，

即ei=ai-2^k+1+ai-2^k+2+....+ai.

4)e中元素的后继（为节点的父亲节点）：结点的后继是比它大的，最近的且编号末尾连续0比e多的结点。

5）e中元素的前驱：结点的前驱为比e小的，最近的且末尾连续0的个数比e多的结点。前驱主要计算连续的和。

例如，Sum(7)=a1+a2+...+a7=e7+e6+e4

基本操作！！！！

1.预备函数 lowbit(int)

  从基本概念可以知道，树状数组最基本的操作就是找到前驱和后继。通过lowbit（）函数可以非常简单地找到前驱和后继结点。

  lowbit()函数是返回将参数转化为二进制数后最后一个1所在的位置，此位置转化为十进制后的值。例如，34转化为二进制

为100010，最后一个1在第二位，所以lowbit返回值为2.

    参考代码

  int lowbit(int k)

{

      return k&(-k);

}

2.修改某一元素的值

   将ak的值增加v,需要把ek以后的后继结点全部增加k，一直到LEN（最大长度）。

  参考代码：

  #define LEN 10000

 int eLEN;

void add(int k,int v)

{

 while(k<=LEN)

{

ek+=v;    k+=lowbit(k);

}

}

三。求原始数据前k项的和

只需把ek以及其前驱结点的值累加即可。

参考代码：

int sum(int k)

{

  int re=0;

while(k>0)

{

  re+=ek;

k-=lowbit(k);

}

return re;

} 

推荐例题：HDU 1166 https://blog.csdn.net/qq_41603898/article/details/81196356

其他例题可查看我的树状数组分类