树状数组

树状数组

树状数组的组成结构：

树上结点C和A数组的关系：

C结点管辖的区域是

，其中k是结点下标二进制末尾0的个数

计算

：

int lowbit(int a){ return a&(a^(a-1)); //return a&(-a); }

则对于一颗子树，父节点和子节点的区域关系：

. 于是有了这样的更新函数：

int update(int i,int x){ while(i<=n){ //x更新C[i] 如C[i]=C[i]+x; i=i+lowbit(i); }}

求数组A前k项和：

如：

int Sum(int k){ int sum=0; while(k>0){ sum+=C[k]; k=k-lowbit(k); } return sum;}

例题：

hdu 2838

hdu 2689

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。