树状数组是一种单点修改并查询前缀和的数据结构

查询和修改时间复杂度都是log（n）

对于树状数组我们首先需要知道lowbit的概念

lowbit即是x & -x

通俗点是一个数二进制下的从后往前数第一个1所对应的值

 

具体算法的话就是两个

一个是修改函数如下

 

1 void add(int pos, int w) 2  3 { 4  5     while(pos <= n) 6  7     { 8  9         c[pos]+=w;10 11         pos+=lowbit(pos);12 13     }14 15 }

 

一个是查询如下

1 int sum(int pos) 2  3 { 4  5     int ret = 0; 6  7     while (pos > 0) 8  9     {10 11         ret+=c[pos];12 13         pos-=lowbit(pos);14 15     }16 17     return ret;18 19 }

 

 

 

 

 

 

很好写也易于理解

我第一次自己写的时候初始赋值错了导致初始化复杂度过大

可以初始赋值的时候就使用add( i , a[i] )