树状数组(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
其他例题可查看我的树状数组分类