树状数组基础
发布时间:2020-12-14 04:25:37 所属栏目:大数据 来源:网络整理
导读:int lowbit( int i){ return i -i; // 或者是return i-(i(i-1));表示求数组下标二进制的非0最低位所表示的值 } void update( int i, int val) // 单点更新 { while (i= n){ C[i] += val; i +=lowbit(i); // 由叶子节点向上更新树状数组C,从左往右更新 }} in
int lowbit(int i) { return i & -i;//或者是return i-(i&(i-1));表示求数组下标二进制的非0最低位所表示的值 } void update(int i,int val)//单点更新 { while(i<=n){ C[i]+=val; i+=lowbit(i);//由叶子节点向上更新树状数组C,从左往右更新 } } int sum(int i)//求区间[1,i]内所有元素的和 { int ret=0; while(i>0){ ret+=C[i];//从右往左累加求和 i-=lowbit(i); } return ret; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |